{--
    Problems from http://projecteuler.net/
    My user name there is ingo (iwechsung)
-}
package examples.Euler where

import frege.Prelude hiding(sum)

import frege.prelude.Math hiding (exp, e, pi)
import Data.TreeMap as TM hiding(union, delete, insert, !!)
import Data.List as DL hiding (lookup)
import Data.Bits
import frege.test.QuickCheckProperty (forAll, `==>`, property)

bigs = Integer.arbitrary


--- Find the sum of all the multiples of 3 or 5 below 1000
problem1 = isum m3 + isum m5 - isum m15 where
    m3 = takeWhile (<1000) $ iterate (3+) 3
    m5 = takeWhile (<1000) $ iterate (5+) 5
    m15= takeWhile (<1000) $ iterate (15+) 15
    

--- Fibonacci numbers as ['Int']
ifibs = 1:1: zipWith (Int.+) ifibs (tail ifibs)
--- Fibonacci numbers as ['Integer']
fibs = 1n:1n: zipWith (Integer.+) fibs (tail fibs)

--- sum of 'Int'
isum xs  = fold (Int.+) 0 xs
iprod xs = fold (Int.*) 1 xs
sum  xs = fold (Integer.+) Integer.zero xs
prod xs = fold (Integer.*) Integer.one  xs

--- the sum of numbers 1..n
sumN n
    | n == Integer.zero = Integer.zero
    | n == Integer.one  = Integer.one
    | n <  Integer.zero = negate (sumN (abs n))
    | otherwise         = (n * (n + Integer.one)) `shiftR` 1    -- divided by 2


--- 'Integer' prime numbers
--  'Integer' prime numbers
primes = 2.big: filter isprime (iterate (2.big +) 3.big)
isprime n | n < 2n = false
isprime n = isp primes n where
    isp (a:as) n
        | a*a > n = true
        | n `rem` a == Integer.zero = false
        | otherwise = isp as n
    isp _ _ = undefined

--- primefactors, find all the prime factors of n in descending order
primefactors n = pfs primes n [] where
    pfs (a:as) n acc
        | a*a > n = n:acc
        | n `rem` a == Integer.zero = pfs (a:as) (n `quot` a) (a:acc)
        | otherwise = pfs as n acc
    pfs _ _ _ = undefined

--- primefactors where equal factors are replaced by their product
uprimefactors n = u (primefactors n) where
    u [] = []
    u as = prod (takeWhile (==head as) as) : u (dropWhile (==head as) as)
        
prop_primefactors = property prop where
    prop big = big > 1n ==> all isprime pfs && descending pfs && prod pfs == abs big where
        pfs = primefactors (abs big)
        descending []  = true
        descending [a] = true
        descending (a:b:rest) = a >= b && descending (b:rest)

--- same as above with int for better performance of problem11
--- prime numbers
iprimes = 2: filter intIsPrime (iterate (2+) 3)
intIsPrime n = n > 1 && isp iprimes n where
        isp (a:as) n
            | a*a > n = true
            | n `rem` a == 0 = false
            | otherwise = isp as n
        isp [] _ = undefined

--- primefactors, find all the prime factors of n in descending order
iprimefactors n = pfs iprimes n [] where
    pfs (a:as) n acc
        | a*a > n = n:acc
        | n `rem` a == 0 = pfs (a:as) (n `div` a) (a:acc)
        | otherwise = pfs as n acc
    pfs _ _ _ = []

--- primefactors in the form [(p,k), ...] where k tells how often p appears
icanonicpfs n = c (iprimefactors n) where
    c [] = []
    c (as@a:_) = (a, length (takeWhile (a==) as)) : c (dropWhile (a==) as)


--- The sum of all the even-valued fibs which do not exceed four million.
--- This employs the fact that every 3rd fib and only every 3rd fib is even
problem2 = isum $ takeWhile (<=4_000_000) (every3rd ifibs) where
    every3rd (_:_:a:as) = a : every3rd as
    every3rd _          = []

--- This is the largest prime factor of the number 600851475143
problem3 = head (primefactors 600851475143L.big)

--- The largest palindrome made from the product of two 3-digit numbers.
--- This returns the palindrome along with the factors in a 3-tuple.
--- must be sorted to get the greatest.

problem4 = head $ sortBy (flip (<=>)) $ [ (p, i, j) | i <- dig3nums, 
                                             j <- reverse [i..999.big], p = i*j, palindrome (show p) ]
    where
        dig3nums = takeWhile (100.big <=) (iterate pred 999.big)

palindrome p = pali p where
        pali ""     = true
        pali ´^\d$´ = true
        pali (m~´^(\d)(\d*)\1$´) | Just s <- m.group 2 = pali s
        pali _ = false

--- The smallest number that can be divided by any number 1..20
problem5 = 232792560.big -- 16*9*5*7*11*13*17*19

--- Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
problem6 = abs $ sumsq - sqsum where
        sumsq = sum [n*n | n <- [1.big .. 100.big]]
        sqsum = let s = sum [ 1.big .. 100.big ] in s*s

--- What is the 10001st prime number?
problem7 = head $ drop 10000 primes

{--
Find the greatest product of five consecutive digits in the 1000-digit number.

    73167176531330624919225119674426574742355349194934
    96983520312774506326239578318016984801869478851843
    85861560789112949495459501737958331952853208805511
    12540698747158523863050715693290963295227443043557
    66896648950445244523161731856403098711121722383113
    62229893423380308135336276614282806444486645238749
    30358907296290491560440772390713810515859307960866
    70172427121883998797908792274921901699720888093776
    65727333001053367881220235421809751254540594752243
    52584907711670556013604839586446706324415722155397
    53697817977846174064955149290862569321978468622482
    83972241375657056057490261407972968652414535100474
    82166370484403199890008895243450658541227588666881
    16427171479924442928230863465674813919123162824586
    17866458359124566529476545682848912883142607690042
    24219022671055626321111109370544217506941658960408
    07198403850962455444362981230987879927244284909188
    84580156166097919133875499200524063689912560717606
    05886116467109405077541002256983155200055935729725
    71636269561882670428252483600823257530420752963450

-}
problem8 = fold max 0 (prods is) where
    is = [ ord c - ord '0' | c <- unpacked s1000 ]
    prods (a:b:c:d:e:rest) = a*b*c*d*e : prods (b:c:d:e:rest)
    prods _ = []
    s1000 = 
        "73167176531330624919225119674426574742355349194934" ++
        "96983520312774506326239578318016984801869478851843" ++
        "85861560789112949495459501737958331952853208805511" ++
        "12540698747158523863050715693290963295227443043557" ++
        "66896648950445244523161731856403098711121722383113" ++
        "62229893423380308135336276614282806444486645238749" ++
        "30358907296290491560440772390713810515859307960866" ++
        "70172427121883998797908792274921901699720888093776" ++
        "65727333001053367881220235421809751254540594752243" ++
        "52584907711670556013604839586446706324415722155397" ++
        "53697817977846174064955149290862569321978468622482" ++
        "83972241375657056057490261407972968652414535100474" ++
        "82166370484403199890008895243450658541227588666881" ++
        "16427171479924442928230863465674813919123162824586" ++
        "17866458359124566529476545682848912883142607690042" ++
        "24219022671055626321111109370544217506941658960408" ++
        "07198403850962455444362981230987879927244284909188" ++
        "84580156166097919133875499200524063689912560717606" ++
        "05886116467109405077541002256983155200055935729725" ++
        "71636269561882670428252483600823257530420752963450"

{-- A Pythagorean triplet is a set of three natural numbers, a  b  c, for which,

    a^2 + b^2 = c^2
    
    For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

    There exists exactly one Pythagorean triplet for which a + b + c = 1000.
    Find the product abc.
-}
problem9 = (a * b * c, (a, b, c)) where
    (a,b,c) = head [(a,b,c) | a <- [1..334], 
                              b <- [a+1 .. 1000-a], 
                              c = 1000-(a+b), c > b, a*a+b*b==c*c]

{--
    Find the sum of all the primes below two million.
-}
problem10 = sum $ takeWhile ( < 2000000.big) primes

{--
    The sequence of triangle numbers is generated by adding the natural numbers. 
    So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. 
    The first ten terms would be:

    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

    Let us list the factors of the first seven triangle numbers:

     1: 1
     3: 1,3
     6: 1,2,3,6
    10: 1,2,5,10
    15: 1,3,5,15
    21: 1,3,7,21
    28: 1,2,4,7,14,28
    We can see that 28 is the first triangle number to have over five divisors.
    
    What is the value of the first triangle number to have over five hundred divisors?
-}
problem11 = head $ filter (\x -> length x > 500) $ map divisors triangles  -- 53 secs

triangles = Integer.one : zipWith (Integer.+) triangles (iterate Integer.succ 2.big)
powerSet [] = [[]]
powerSet (a:as) = let ps = powerSet as in ps ++ map (a:) ps
divisors n   | n == Integer.one = [Integer.one]
divisors n = go (head primes) [Integer.one,n] where
    go i acc | sqr > n        = acc
             | sqr == n       = i:acc
             | n `rem` i == Integer.zero 
                              = go (i+Integer.one) (i : n `div` i : acc)
             | otherwise      = go (i+Integer.one) acc
             where sqr = i*i
properDivisors n = filter (<n) (divisors n)

amicablePair n = if d b == n then b else n where
    b = d n
    d = isum • iproperDivisors


itriangles = 1 : zipWith (Int.+) itriangles (iterate Int.succ 2)
idivisors 1 = [1]
idivisors n = go 2 [1,n] where
    go i acc | sqr > n        = acc
             | sqr == n       = i:acc
             | n `rem` i == 0 = go (i+1) (i : n `div` i : acc)
             | otherwise      = go (i+1) acc
             where sqr = i*i
iproperDivisors n = filter (<n) (idivisors n)
iproblem11 = head $ filter (\x -> length x > 500) $ map idivisors itriangles

{--
    Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.
-}


problem13 = first10 (sum nums) where
    tenBillion = 10_000_000_000N    --(ten*ten*ten) * (ten*ten*ten) * (ten*ten*ten) * ten
    !ten = 10n
    first10 n 
        | n >= tenBillion = first10 (n `quot` ten)
        | otherwise = n
    nums = [
            37107287533902102798797998220837590246510135740250n,
            "46376937677490009712648124896970078050417018260538".aton,
            "74324986199524741059474233309513058123726617309629".aton,
            "91942213363574161572522430563301811072406154908250".aton,
            "23067588207539346171171980310421047513778063246676".aton,
            "89261670696623633820136378418383684178734361726757".aton,
            "28112879812849979408065481931592621691275889832738".aton,
            "44274228917432520321923589422876796487670272189318".aton,
            "47451445736001306439091167216856844588711603153276".aton,
            "70386486105843025439939619828917593665686757934951".aton,
            "62176457141856560629502157223196586755079324193331".aton,
            "64906352462741904929101432445813822663347944758178".aton,
            "92575867718337217661963751590579239728245598838407".aton,
            "58203565325359399008402633568948830189458628227828".aton,
            "80181199384826282014278194139940567587151170094390".aton,
            "35398664372827112653829987240784473053190104293586".aton,
            "86515506006295864861532075273371959191420517255829".aton,
            "71693888707715466499115593487603532921714970056938".aton,
            "54370070576826684624621495650076471787294438377604".aton,
            "53282654108756828443191190634694037855217779295145".aton,
            "36123272525000296071075082563815656710885258350721".aton,
            "45876576172410976447339110607218265236877223636045".aton,
            "17423706905851860660448207621209813287860733969412".aton,
            "81142660418086830619328460811191061556940512689692".aton,
            "51934325451728388641918047049293215058642563049483".aton,
            "62467221648435076201727918039944693004732956340691".aton,
            "15732444386908125794514089057706229429197107928209".aton,
            "55037687525678773091862540744969844508330393682126".aton,
            "18336384825330154686196124348767681297534375946515".aton,
            "80386287592878490201521685554828717201219257766954".aton,
            "78182833757993103614740356856449095527097864797581".aton,
            "16726320100436897842553539920931837441497806860984".aton,
            "48403098129077791799088218795327364475675590848030".aton,
            "87086987551392711854517078544161852424320693150332".aton,
            "59959406895756536782107074926966537676326235447210".aton,
            "69793950679652694742597709739166693763042633987085".aton,
            "41052684708299085211399427365734116182760315001271".aton,
            "65378607361501080857009149939512557028198746004375".aton,
            "35829035317434717326932123578154982629742552737307".aton,
            "94953759765105305946966067683156574377167401875275".aton,
            "88902802571733229619176668713819931811048770190271".aton,
            "25267680276078003013678680992525463401061632866526".aton,
            "36270218540497705585629946580636237993140746255962".aton,
            "24074486908231174977792365466257246923322810917141".aton,
            "91430288197103288597806669760892938638285025333403".aton,
            "34413065578016127815921815005561868836468420090470".aton,
            "23053081172816430487623791969842487255036638784583".aton,
            "11487696932154902810424020138335124462181441773470".aton,
            "63783299490636259666498587618221225225512486764533".aton,
            "67720186971698544312419572409913959008952310058822".aton,
            "95548255300263520781532296796249481641953868218774".aton,
            "76085327132285723110424803456124867697064507995236".aton,
            "37774242535411291684276865538926205024910326572967".aton,
            "23701913275725675285653248258265463092207058596522".aton,
            "29798860272258331913126375147341994889534765745501".aton,
            "18495701454879288984856827726077713721403798879715".aton,
            "38298203783031473527721580348144513491373226651381".aton,
            "34829543829199918180278916522431027392251122869539".aton,
            "40957953066405232632538044100059654939159879593635".aton,
            "29746152185502371307642255121183693803580388584903".aton,
            "41698116222072977186158236678424689157993532961922".aton,
            "62467957194401269043877107275048102390895523597457".aton,
            "23189706772547915061505504953922979530901129967519".aton,
            "86188088225875314529584099251203829009407770775672".aton,
            "11306739708304724483816533873502340845647058077308".aton,
            "82959174767140363198008187129011875491310547126581".aton,
            "97623331044818386269515456334926366572897563400500".aton,
            "42846280183517070527831839425882145521227251250327".aton,
            "55121603546981200581762165212827652751691296897789".aton,
            "32238195734329339946437501907836945765883352399886".aton,
            "75506164965184775180738168837861091527357929701337".aton,
            "62177842752192623401942399639168044983993173312731".aton,
            "32924185707147349566916674687634660915035914677504".aton,
            "99518671430235219628894890102423325116913619626622".aton,
            "73267460800591547471830798392868535206946944540724".aton,
            "76841822524674417161514036427982273348055556214818".aton,
            "97142617910342598647204516893989422179826088076852".aton,
            "87783646182799346313767754307809363333018982642090".aton,
            "10848802521674670883215120185883543223812876952786".aton,
            "71329612474782464538636993009049310363619763878039".aton,
            "62184073572399794223406235393808339651327408011116".aton,
            "66627891981488087797941876876144230030984490851411".aton,
            "60661826293682836764744779239180335110989069790714".aton,
            "85786944089552990653640447425576083659976645795096".aton,
            "66024396409905389607120198219976047599490197230297".aton,
            "64913982680032973156037120041377903785566085089252".aton,
            "16730939319872750275468906903707539413042652315011".aton,
            "94809377245048795150954100921645863754710598436791".aton,
            "78639167021187492431995700641917969777599028300699".aton,
            "15368713711936614952811305876380278410754449733078".aton,
            "40789923115535562561142322423255033685442488917353".aton,
            "44889911501440648020369068063960672322193204149535".aton,
            "41503128880339536053299340368006977710650566631954".aton,
            "81234880673210146739058568557934581403627822703280".aton,
            "82616570773948327592232845941706525094512325230608".aton,
            "22918802058777319719839450180888072429661980811197".aton,
            "77158542502016545090413245809786882778948721859617".aton,
            "72107838435069186155435662884062257473692284509516".aton,
            "20849603980134001723930671666823555245252804609722".aton,
            "53503534226472524250874054075591789781264330331690".aton]
            
{--
    The following iterative sequence is defined for the set of positive integers:
    
    > n  = n/2 (n is even)
    > n  = 3n + 1 (n is odd)
    
    Using the rule above and starting with 13, we generate the following sequence:
    
    > 13  40  20  10  5  16  8  4  2  1
    
    It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. 
    Although it has not been proved yet (Collatz Problem), 
    it is thought that all starting numbers finish at 1.
    
    Which starting number, under one million, produces the longest chain?
-}
problem14 = fold longest (1, [1.big]) (map (iter []) [2.big .. 999999.big]) where
        longest (n,a) b = let m = length b in if n > m then (n,a) else (m, reverse b)
        iter acc n
            | n == Integer.one = n:acc
            | (n .&. Integer.one) == Integer.zero = iter (n:acc) (n `shiftR` 1)   -- even
            | otherwise = iter (n:acc) ((n `shiftL` 1) + n + Integer.one)
--- because problem14 takes 61 seconds, we use an Array to cache results.
{- problem14e has runtime 3.416 sec.
problem14e = longest 2 (1, 1) where
        arr = IntArr.new 1000000
        longest i (inx, len)
            | i >= arr.length = (inx, len)
            | otherwise = do
                    arr.[i <- iter 0 i.big]
                    -- stdout << "arr.[" << i << "] = " << arr.[i] << "\n"
                for if arr.[i] > len then longest (i+1) (i, arr.[i]) else longest (i+1) (inx, len)
        iter !acc !n
            | n == Integer.one = 1+acc
            | n < arr.length.big, have <- arr.[n.int], have > 0 = have + acc
            | n `.&.` Integer.one == Integer.zero = iter (1+acc) (n `shiftR` 1)   -- even
            | otherwise = iter (1+acc) ((n `shiftL` 1) + n + Integer.one)
-}

-- trying to write problem14 as an array transformer
{-
data STA t =
        STA (IntArr -> (t, IntArr))
        | BND ((STA t), (t -> STA t))
    where
        native coerce new :: Int -> (STA a , (a -> STA b)) -> STA b
        
        eval (STA f) arr    = f arr
        eval (BND (m, k)) arr  = case eval m arr of
            (a, arr2) -> eval (k a) arr2 
        block size m = let (a, _) = eval m (IntArr.new size) in a
        fetch i     = STA (\(x::IntArr) -> (x.[i]; x))
        store i v   = STA (\(x::IntArr) -> (x.[i <- v]; x))
        länge       = STA (\(x::IntArr) -> (x.length; x))
        roArray     = STA (\(x::IntArr) -> (\i -> x.[i]; x))

    
instance Monad STA where
    return a = STA (\(x::IntArr) -> (a; x)) 
    m >>= k = STA.coerce 1 (m,k)
    m1 >> m2 = m1 >>= (\_ -> m2)
    
    
problem14m i = STA.block i (loop) where
        loop = do
                j <- STA.länge
                foldM (maxlen j) (1,1) (2..(j-1))
            where 
                maxlen limit (inx, len) i = do
                    indexfun <- STA.roArray                    
                    v = iter indexfun 0 limit.big i.big
                    STA.store i v
                    if (v > len) then STA.return (i; v) else STA.return (inx; len)
        
        iter :: (Int -> Int) -> Int -> Integer -> Integer -> Int
        iter inx acc limit n
            | n < limit, cached > 0 = (acc+cached)
            | n == Integer.one = 1+acc
            | n `.&.` Integer.one == Integer.zero = iter inx (1+acc) limit (n `shiftR` 1)   -- even
            | otherwise = iter inx (1+acc) limit ((n `shiftL` 1) + n + Integer.one)          -- odd
            where cached = inx n.int
-}

fret a x = (a, x)
fbind :: (x -> (a,x)) -> (a -> x -> (b,x)) -> (x -> (b,x))
fbind !m k x = case m x of (!a, !x') -> k a x'
fthen !m1 m2 x = case m1 x of (_, !x') -> m2 x' 

--- problem14 with pure functions
{-
problem14f n = block n loop
    where
        block size m = let (a, _) = m (IntArr.new size) in a
        fetch i     = (\(x::IntArr) -> (x.[i]; x))
        store i v   = (\(x::IntArr) -> (x.[i <- v]; x))
        länge       = (\(x::IntArr) -> (x.length; x))
        -- foldF :: (a -> b -> (s -> (a,s))) -> a -> [b] -> (s -> (a,s))
        foldF f a [] = fret a
        foldF f a (x:xs) = f a x `fbind`  (\fax -> foldF f fax xs)
        loop = länge `fbind` (\j -> foldF (maxlen j) (1,1) (2..(j-1)))
            where 
                maxlen limit (inx, len) i = iter 0 i.big limit.big `fbind` (\v ->
                                        store i v `fthen` 
                                        (if v > len then fret (i;v) else fret (inx;len)
                                      ))
        iter acc n limit 
            | n < limit = fetch (n::Integer).int `fbind`(\have ->
                                    (if have > 0 then fret (have+acc) else iter' acc n limit))
            | otherwise = iter' acc n limit 
                
        iter' acc n limit
            | n == Integer.one = fret (1+acc)
            | n `.&.` Integer.one == Integer.zero = iter (1+acc) (n `shiftR` 1) limit  -- even
            | otherwise = iter (1+acc) ((n `shiftL` 1) + n + Integer.one) limit
-}        
{--
    2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

    What is the sum of the digits of the number 2^1000?
-}
problem16 = isum [ ord c - ord '0' | c <- unpacked str ] where
        twoExp1000 = Integer.one `shiftL` 1000 -- 2^1000
        str = show twoExp1000

{--
    If the numbers 1 to 5 are written out in words: one, two, three, four, five, then 
    there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

    If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, 
    how many letters would be used? 

    NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) 
    contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. 
    The use of "and" when writing out numbers is in compliance with British usage.
-}
problem17 =  isum (map length (map say [1..999])) + length "oneThousand"
say 0 = ""
say 1 = "One"
say 2 = "Two"
say 3 = "Three"
say 4 = "Four"
say 5 = "Five"
say 6 = "Six"
say 7 = "Seven"
say 8 = "Eight"
say 9 = "Nine"
say 10 = "Ten"
say 11 = "Eleven"
say 12 = "Twelve"
say 13 = "Thirteen"
say 15 = "Fifteen"
say 18 = "Eighteen"
say n | n < 20 = say (n `rem` 10) ++ "teen"
say 20 = "Twenty"
say 30 = "Thirty"
say 40 = "Forty"
say 50 = "Fifty"
say 60 = "Sixty"
say 70 = "Seventy"
say 80 = "Eighty"
say 90 = "Ninety"
say n | n < 100 = say zehner ++ say einer where
     einer = n `rem` 10
     zehner = n - einer
say n | rest == 0 = say (n `div` 100) ++ "Hundred"
      | otherwise = say (n `div` 100) ++ "HundredAnd" ++ say rest where
        rest = n `rem` 100


{--
    By starting at the top of the triangle below and moving to adjacent numbers on the row below, 
    the maximum total from top to bottom is 23.

    >    3
    >   7 5
    >  2 4 6
    > 8 5 9 3

    That is, 3 + 7 + 4 + 9 = 23.

    Find the maximum total from top to bottom of the triangle below:

    >                   75
    >                 95 64
    >                17 47 82
    >              18 35 87 10
    >             20 04 82 47 65
    >            19 01 23 75 03 34
    >           88 02 77 73 07 63 67
    >          99 65 04 28 06 16 70 92
    >         41 41 26 56 83 40 80 70 33
    >        41 48 72 33 47 32 37 16 94 29
    >       53 71 44 65 25 43 91 52 97 51 14
    >      70 11 33 28 77 73 17 78 39 68 17 57
    >     91 71 52 38 17 14 91 43 58 50 27 29 48
    >   63 66 04 68 89 53 67 30 73 16 69 87 40 31
    > 04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

    NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, 
    Problem 67, is the same challenge with a triangle containing one-hundred rows; 
    it cannot be solved by brute force, and requires a clever method! ;o)

-}

problem18 = maxsum (reverse triangle) where
    check n (ns:nss)
        | n == length ns = ns : check (n+1) nss
        | otherwise = error ("bad triangle row " ++ show n)
    check n []
        | n > 1 = []
        | otherwise = error ("empty triangle")
    maxsum (al:au:as) = maxsum (an:as) where
        an = zipWith (Int.+) ar au
        ar = zipWith (Int.max) al (tail al)
    maxsum [[n]] = n
    maxsum bad = error ("bad triangle: " ++ show bad)    
    triangle =  check 1  -- [[Int]]
                     [[                   75                                        ],
                      [                 95, 64                                      ],
                      [                17, 47, 82                                   ],
                      [              18, 35, 87, 10                                 ],
                      [             20,  4, 82, 47, 65                              ],
                      [            19,  1, 23, 75,  3, 34                           ],
                      [           88,  2, 77, 73,  7, 63, 67                        ],
                      [          99, 65,  4, 28,  6, 16, 70, 92                     ],
                      [         41, 41, 26, 56, 83, 40, 80, 70, 33,                 ],
                      [        41, 48, 72, 33, 47, 32, 37, 16, 94, 29,              ],
                      [       53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14            ],
                      [      70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57         ],
                      [     91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48      ],
                      [   63, 66,  4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31,   ],
                      [  4, 62, 98, 27, 23,  9, 70, 98, 73, 93, 38, 53, 60,  4, 23  ]]

{--
    You are given the following information, but you may prefer to do some research for yourself.
    
    - 1 Jan 1900 was a Monday. 
    - Thirty days has September,
    April, June and November.
    All the rest have thirty-one,
    Saving February alone,
    Which has twenty-eight, rain or shine.
    And on leap years, twenty-nine. 
    - A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400. 
    How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?
-}
problem19 = nsun 0 start where
    start = ymd 1901 1 6                -- first sunday in 1901 was Jan, 6
    ymd :: Int -> Int -> Int -> Int     -- pack year, month, day in an int
    ymd a b c = (a `shiftL` 16) .|. (b `shiftL` 8) .|. c
    year :: Int -> Int                  -- unpack year
    year ymd = ymd `shiftR` 16
    mon :: Int -> Int                   -- unpack month
    mon ymd  = (ymd `shiftR` 8) .&. 255
    day :: Int -> Int                   -- unpack day
    day ymd  = ymd .&. 255
    days :: Int -> Int -> Int           -- how many days in month of year
    days year 2  = if leapyear year then 29 else 28
    days year 4  = 30
    days year 6  = 30
    days year 9  = 30
    days year 11 = 30
    days _    _  = 31
    leapyear y = (y `rem` 4 == 0) && (y `rem` 100 != 0 || y `rem` 400 == 0)
    nsun n date
        | year date > 2000 = n
        | day date == 1 = nsun (n+1) (next date)
        | otherwise     = nsun n (next date)
    next date = ymd y' m' d' where
        d = day date
        m = mon date
        y = year date
        md = days y m
        d' = if d+7 > md then d + 7 - md else d+7
        m' = if d+7 > md then if m==12 then 1 else m+1 else m
        y' = if d+7 > md && m' == 1 then y+1 else y

{--
    n! means n \*(n-1)\* ...  3\*2\*1

    Find the sum of the digits in the number 100!
-}
problem20 = (sum • digits • fac) 100.big where
    fac n = prod [1.big .. n]
    !ten = 10.big
    digits n 
        | n == Integer.zero = []
        | otherwise = n `rem` ten : digits (n `div` ten)

{--
     Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
    If d(a) = b and d(b) = a, where a  != b, then a and b are an amicable pair 
    and each of a and b are called amicable numbers.

    For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. 
    The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

    Evaluate the sum of all the amicable numbers under 10000.
-}

problem21 = (isum • filter isAmicable) [1..10000] where
    isAmicable n = amicablePair n != n

{--
    Using names.txt a 46K text file containing over five-thousand first names, 
    begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, 
    multiply this value by its alphabetical position in the list to obtain a name score.

    For example, when the list is sorted into alphabetical order, COLIN, 
    which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. 
    So, COLIN would obtain a score of 938 * 53 = 49714.

    What is the total of all the name scores in the file?
-}
problem22 file = withFile result
    where
        result = (isum • score  • sort • map extract • ´,\s*´.splitted • fold (++) "")
        extract (m ~ ´"(\w+)"´) = unJust (m.group 1)
        extract _ = ""
        score = zipWith scoreOne (iterate (1+) 1)
        scoreOne num str = num * isum [ ord c - ord 'A' + 1 | c <- unpacked str ]

{--
    A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. 
    For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, 
    which means that 28 is a perfect number.

    A number whose proper divisors are less than the number is called deficient 
    and a number whose proper divisors exceed the number is called abundant.

    As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, 
    the smallest number that can be written as the sum of two abundant numbers is 24. 
    
    By mathematical analysis, it can be shown that all integers greater than 28123 
    can be written as the sum of two abundant numbers. 
    However, this upper limit cannot be reduced any further by analysis even though it is known 
    that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

    Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
-}
{-
problem23x = (isum • filter notSum) (1..28123) where
    !abuArr = IntArr.fromList abundants
    !sumArr = outer (IntArr.new 28124) 0 -- [ a + b | a <- abundants, b <- abundants, b<a, a+b < 28124 ]
    outer :: IntArr -> Int -> IntArr
    outer !arr !ai | ai < abuArr.length = outer (inner arr abuArr.[ai] 0) (ai+1)
                   | otherwise = arr
    inner :: IntArr -> Int -> Int -> IntArr
    inner !arr !a !bi | bi < abuArr.length, b <- abuArr.[bi], b <= a, a+b < 28124 = do arr.[a+b <- 1]; inner arr a (bi+1)
                   | otherwise = arr
    notSum n = sumArr.[n] == 0   
-}    

problem23 = (isum • filter noSum) [1..28123] where
    -- a number /i/ is a sum of 2 abundant numbers if there is an /a/ from the set of abundant numbers
    -- such that a<i and i-a is itself an abundant number
   
    -- a number /i/ is not the sum of two abundant numbers if there does not exist an abundant number /a/,
    -- such that a < i and (i-a) is itself abundant.
    noSum i = null [ a | a <- abundants, a<i, 
                         isJust (abtree.lookup (i-a)) ] 
                        -- abuarr.[i-a] != 0]
    -- list of abundant numbers up to 28123
    abundants = [ i | i <- [1 .. 28123], isum (iproperDivisors i) > i ]
    -- the set of abundant numbers up to 28123
    abtree = fold (\t\a -> TreeMap.insert t a ()) TreeMap.empty abundants
    -- abuarr = IntArr.fromInxList (zip abundants (repeat 1))
                            
-- with array: 2.41 wallclock seconds.
-- with tree: 14.903 wallclock seconds.

{--
    A permutation is an ordered arrangement of objects. 
    For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. 
    If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. 
    The lexicographic permutations of 0, 1 and 2 are:

    012   021   102   120   201   210

    What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
-}
longds = [0L..9L]
problem24 = head $ drop 999999 [ a*1_000_000_000L + b*100_000_000L + c*10_000_000L
                                +d*1_000_000L + e*100_000L + f*10_000L + g*1_000L + h*100L + i*10L + j |
                    a <- longds, 
                    b <- longds, b != a,
                    c <- longds, c != a, c != b,
                    d <- longds, d != a, d != b, d != c,
                    e <- longds, e != a, e != b, e != c, e != d,
                    f <- longds, f != a, f != b, f != c, f != d, f != e,
                    g <- longds, g != a, g != b, g != c, g != d, g != e, g != f,
                    h <- longds, h != a, h != b, h != c, h != d, h != e, h != f, h != g,
                    i <- longds, i != a, i != b, i != c, i != d, i != e, i != f, i != g, i != h,
                    j <- longds, j != a, j != b, j != c, j != d, j != e, j != f, j != g, j != h, j != i ]

{--
    The Fibonacci sequence is defined by the recurrence relation:

    Fn = Fn-1 + Fn-2, where F1 = 1 and F2 = 1.
    Hence the first 12 terms will be:

    F1 = 1
    F2 = 1
    F3 = 2
    F4 = 3
    F5 = 5
    F6 = 8
    F7 = 13
    F8 = 21
    F9 = 34
    F10 = 55
    F11 = 89
    F12 = 144
    
    The 12th term, F12, is the first term to contain three digits.

    What is the first term in the Fibonacci sequence to contain 1000 digits?

 -}
exp n 0 = 1n
exp n 1 = n
exp n i
    | i `rem` 2 == 0 = let j = i `div` 2; nn = exp n j in nn*nn
    | otherwise = n * exp n (i-1)

iexp n 0 = 1
iexp n 1 = n
iexp n i
    | (i .&. 1) == 0 = let j = i `div` 2; nn = iexp n j in nn*nn
    | otherwise = n * iexp n (i-1)

problem25 a = loop 3 1n 1n where
    limit = (10n `exp` a) 
    loop !f !n1 !n2 | n3 >= limit = (f, n3)
                    | otherwise = loop (f+1) n2 n3
                    where n3 = n1 + n2

{--
    A unit fraction contains 1 in the numerator. 
    The decimal representation of the unit fractions with denominators 2 to 10 are given:

    1/2 =  0.5 
    1/3 =  0.(3) 
    1/4 =  0.25 
    1/5 =  0.2 
    1/6 =  0.1(6) 
    1/7 =  0.(142857) 
    1/8 =  0.125 
    1/9 =  0.(1) 
    1/10 =  0.1 

    Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. 
    It can be seen that 1/7 has a 6-digit recurring cycle.

    Find the value of d  1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.
-}

fraction fracs 0 dem  = []
fraction  fracs nom dem
    | nom >= dem  = error "nom >= dem"
    | nom `elem` (map snd fracs) = dropUntil (\(f,n) -> n == nom) (reverse fracs)
    | otherwise =  fraction ((nom*10 `div` dem, nom):fracs) (nom*10 `rem` dem) dem

problem26 = (head 
                • sortBy (comparing (length•snd) ) 
                • map (\d -> (d, fraction [] 1 d))) [2..999] 



{--
    Euler published the remarkable quadratic formula:

            n� + n + 41

    It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. 
    However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, 
    and certainly when n = 41, 41� + 41 + 41 is clearly divisible by 41.

    Using computers, the incredible formula  n� - 79n + 1601 was discovered, 
    which produces 80 primes for the consecutive values n = 0 to 79. 
    The product of the coefficients, 79 and 1601, is 126479.

    Considering quadratics of the form:

    n� + an + b, where |a| < 1000 and |b| < 1000
        where |n| is the modulus/absolute value of n
        e.g. |11| = 11 and |-4| = 4
        
    Find the product of the coefficients, a and b, for the quadratic expression that produces the 
    maximum number of primes for consecutive values of n, starting with n = 0.
-}
derive Show (a,b,c,d)

yieldsPrim n a b = intIsPrime (n*n + a*n + b)
numOfPrimes a b = loop 0 0 a b where
    loop acc n a b = if yieldsPrim n a b then loop (acc+1) (n+1) a b else acc
problem27 limit = (a*b, a, b, nPrimes) where
    (a, b, nPrimes) = (head • sortBy (\(a1,b1,n1)\(a2,b2,n2) -> n2 <=> n1))
        [(a,b, numOfPrimes a b) |
            a <- [negate (limit-1) .. (limit-1)], b <- takeWhile (<limit) iprimes ]

problem29 limit = (length • uniq • sort) [ a `exp` b | 
                        a <- [2n .. Int.big limit], 
                        b <- [2 .. limit] ]

{--
    Surprisingly there are only three numbers that can be written 
    as the sum of fourth powers of their digits:
    
    1634 = 1^4 + 6^4 + 3^4 + 4^4
    8208 = 8^4 + 2^4 + 0^4 + 8^4
    9474 = 9^4 + 4^4 + 7^4 + 4^4
    As 1 = 1^4 is not a sum it is not included.
    
    The sum of these numbers is 1634 + 8208 + 9474 = 19316.
    
    Find the sum of all the numbers that can be written as the 
    sum of fifth powers of their digits.
    
-}
-- what about 828? I suspect we talk about Armstrong numbers (n digit, where the nth-power of each digit
-- adds up to the number
isSumPower k n | n < 10 = false
isSumPower k n = (toInteger n) == (sum • map (`exp` k)) d  where
       d = map (Int.big) (digits n)
       digits 0 = []
       digits n  = n `rem` 10 : digits (n `div` 10)

problem30 n = (isum • filter (isSumPower 5)) [1 .. 354294]   -- 6*(9^5)

{--
    In England the currency is made up of pound, L, and pence, p, 
    and there are eight coins in general circulation:

    1p, 2p, 5p, 10p, 20p, 50p, L1 (100p) and L2 (200p).
    It is possible to make L2 in the following way:

    1L1 + 150p + 220p + 15p + 12p + 31p
    How many different ways can L2 be made using any number of coins?
-}
coins = [200, 100, 50, 20, 10, 5, 2, 1]
waysToChange pence [] = []
waysToChange 0 _      = []
waysToChange pence (p:ps)
    | pence <  p  =  waysToChange pence ps
    | pence == p  = [p]: waysToChange pence ps
    | pence >  p  = map (p:) (waysToChange (pence-p) (p:ps)) ++ waysToChange pence ps
    | otherwise   = undefined
problem31 n = length ( waysToChange n coins )

nWTC _ [] = 0
nWTC 0 _  = 0
nWTC n (kks@k:ks)
    | n <  k = nWTC n ks
    | n == k = 1 + nWTC n ks
    | otherwise = nWTC (n-k) kks + nWTC n ks 
{--
    We shall say that an n-digit number is pandigital if it makes use of all the digits 
    1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

    The product 7254 is unusual, as the identity, 39  186 = 7254, containing multiplicand, multiplier, 
    and product is 1 through 9 pandigital.

    Find the sum of all products whose multiplicand/multiplier/product identity can be written 
    as a 1 through 9 pandigital.

    HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.
-}
-- use a 'Long' as set of 0..63
isIn i set = unitSet i .&. set
unitSet i  = 1L `shiftL` i
emptySet   = 0L

digitSet i = loop emptySet i where
    loop set 0 = set
    loop set i = loop (set .|. unitSet (i `rem` 10)) (i `div` 10)

ds2i acc [] = acc
ds2i acc (a:as) = ds2i (acc*10 + a) as

digits acc 0 = acc
digits acc x = digits (x `rem` 10 : acc) (x `div` 10)


pandigital [] = true
pandigital (0:_) = false
pandigital (x:xs) = x `notElem` xs && pandigital xs 


rotations as = take (length as) . iterate singleRotate $ as 
    where singleRotate [] = [] 
          singleRotate (a:as) = as ++ [a]


problem32 = loop 0 1 where
    loop summe c 
        | c > 99_999 = summe
        | pandigital dsc, !(null (panProduct dsc c)) = loop (summe+c) (c+1)
        | otherwise = loop summe (c+1)
        where
            dsc = digits [] c
            
panProduct dsc c = [ (a,b) |
                        a <- iproperDivisors c,
                        a != 1,
                        dsa = digits [] a,
                        b = c `div` a,
                        dsb = digits [] b,
                        pandigital dsa && 
                            all (`notElem` dsc) dsa &&
                            length dsc + length dsa + length dsb == 9 &&
                            pandigital dsb &&
                            all (`notElem` dsc) dsb &&
                            all (`notElem` dsa) dsb
                        
                        -- aps <- (powerSet <~ filter (`notElem` cps)) (1..9), !(null aps),
                        -- bps <- (powerSet <~ filter (`notElem` aps) <~ filter (`notElem` cps)) (1..9), !(null bps),
                        -- length cps + length bps + length aps == 9, 
                        -- a <- map (ds2i 0) (permutations aps),
                        -- b <- map (ds2i 0) (permutations bps),
                        -- a*b == c 
                ]  

{--
    The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it 
    may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

    We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

    There are exactly four non-trivial examples of this type of fraction, 
    less than one in value, and containing two digits in the numerator and denominator.

    If the product of these four fractions is given in its lowest common terms, 
    find the value of the denominator.
-}
ndigits x = loop [] x where
    loop acc n | n < 10n = n:acc
    loop acc x  = loop (x `rem` 10n : acc) (x `div` 10n)
ds2n ds = loop 0n ds where
    loop acc [] = acc
    loop acc (n:ns) = loop (acc*10n+n) ns

ldigits x = loop [] x where
    loop acc n | n < 10L = n:acc
    loop acc x  = loop (x `rem` 10L : acc) (x `div` 10L)
ds2l ds = loop 0L ds where
    loop acc [] = acc
    loop acc (n:ns) = loop (acc*10L+n) ns

ds2in ds = loop 0n ds where
    loop acc [] = acc
    loop acc (n:ns) = loop (acc*10n + Integer.fromInt n) ns


type Fraction = (Integer, Integer)
-- pure native gcd :: Integer -> Integer -> Integer

reduced   (a,b) = if g > 1n then (a `quot` g, b `quot` g) else (a,b) where g = gcd a b
reducible (a,b) = (a,b) != reduced (a,b)
(a,b) `rlt`   (c,d) =  a*d < b*c
(a,b) `rplus` (c,d) = (a*d + c*b, b*d)
(a,b) `rmul`  (c,d) = (a*c, b*d)
problem33 =  ((reduced . fold rmul (1n,1n)) nums, nums)
    where nums = [ (d,n) | n <- [11n .. 99n], d <- [10n..(n-1n)],
                d `rem` 10n != 0n && n `rem` 10n != 0n,      -- eliminate trivial cases
                ds = ndigits d,
                ns = ndigits n,
                any (`elem` ds) ns,                          -- they do have a digit in common
                reduced (d,n) == reduced (prod ds, prod ns) ]

{--
    145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

    Find the sum of all numbers which are equal to the sum of the factorial of their digits.

    Note: as 1! = 1 and 2! = 2 are not sums they are not included.

-}
idigits x = loop [] x where
    loop acc n | n < 10 = n:acc
    loop acc n  = loop (n `rem` 10 : acc) (n `div` 10)
    
problem34 = ((isum • filter wanted) [10 .. limit], limit) where
    wanted x = x == isum (map fac (idigits x))
    fac 0 = 1
    fac 1 = 1
    fac 2 = 2
    fac 3 = 6
    fac 4 = 24
    fac 5 = 120
    fac 6 = 720
    fac 7 = 5040
    fac 8 = 40320
    fac 9 = 362880
    fac _ = undefined
    limit = (some 1) where
        some n 
            | n * fac 9 > (10n `exp` n).int = some (n+1)
            | otherwise = (n-1) * fac 9 + 1

{--
    The number, 197, is called a circular prime because all rotations of the digits: 
    197, 971, and 719, are themselves prime.

    There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

    How many circular primes are there below one million?
-}
problem35 limit = length . filter isCircularPrime . takeWhile (< limit) $ iprimes
    where    
        isCircularPrime n = all (intIsPrime . ds2i 0) (rotations $ idigits n)            

{--
    The decimal number, 585 = 1001001001 (binary), is palindromic in both bases.

    Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

    (Please note that the palindromic number, in either base, may not include leading zeros.)
-}

problem36 limit = isum • filter binaryPalindrome • filter decimalPalindrome $ [1..limit]
    where
        decimalPalindrome n  = palindrome (show n)
        binaryPalindrome n   = palindrome (showbin n) where
            showbin n = loop "" n where
                loop str 0 = "0" ++ str
                loop str 1 = "1" ++ str
                loop str n | n `rem` 2 == 0 = loop ("0" ++ str) (n `shiftR` 1)
                           | otherwise      = loop ("1" ++ str) (n `shiftR` 1)

{--
    The number 3797 has an interesting property. Being prime itself, 
    it is possible to continuously remove digits from left to right, 
    and remain prime at each stage: 3797, 797, 97, and 7. 
    Similarly we can work from right to left: 3797, 379, 37, and 3.

    Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

    NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
-}
problem37 = sumtup . take 11 . filter truncatableBoth $ dropWhile ( < 8n) primes
    where
        sumtup xs = (sum xs, xs)
        truncatableBoth n = all isprime (takeWhile (> 0n) (iterate (`div` 10n) n))
                            && all (isprime . ds2n) (take (length ds) (iterate tail ds)) where ds = ndigits n 


{--
    Take the number 192 and multiply it by each of 1, 2, and 3:

    192 * 1 = 192
    192 * 2 = 384
    192 * 3 = 576
    
    By concatenating each product we get the 1 to 9 pandigital, 192384576. 
    We will call 192384576 the concatenated product of 192 and (1,2,3)

    The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, 
    giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

    What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product 
    of an integer with (1,2, ... , n) where n > 1?
-}
problem38 = fold max 0 [ ds2i 0 pan |
                i <- [1000..9999],
                pandigital (idigits i),  -- if it is not, double digits will occur in 1*i
                k <- [2..9],
                pan = fold (++) [] (map (idigits • (i*)) [1..k]),
                length pan == 9,
                pandigital pan
            ]

{--
    If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, 
    there are exactly three solutions for p = 120.

    {20,48,52}, {24,45,51}, {30,40,50}

    For which value of p <= 1000, is the number of solutions maximised?
    
    (840, [(40, 399, 401), (56, 390, 394), (105, 360, 375), (120, 350, 370), (140, 336, 364), (168, 315, 357), (210, 280, 350), (240, 252, 348)])
    boxes: 167425064, evals: 418317620 (nat 59%, alg 0%, lazy 20%, re 20%)  runtime 41.372 sec.
    with frege3: runtime 25.486 wallclock seconds
    by constraining a and b a bit more: runtime 7.669 wallclock seconds.
-}
problem39 maxp = fold bestSolution (0, []) . map periSolution . takeWhile (<=maxp) . iterate (2+) $ 2 where
    bestSolution (a, as) (b, bs) | length as <= length bs = (b, bs)
                                 | otherwise = (a, as)
    -- periSolution n | n `rem` 2 != 0 = (n, [])                  -- no solution for odd numbers
    periSolution n = (n, [ (a,b,c) | 
                            a <- [1 .. n `quot` 4],                  -- short side
                            b <- [a .. (n-a) `quot` 2],              -- long side
                            c = n-a-b, c > 0,
                            c*c == a*a + b*b]) 
                                                                 
{--
    An irrational decimal fraction is created by concatenating the positive integers:

    0.123456789101112131415161718192021...

    It can be seen that the 12th digit of the fractional part is 1.

    If dn represents the nth digit of the fractional part, find the value of the following expression.

    d1  d10  d100  d1000  d10000  d100000  d1000000
-}
irrafrac = [ d | i <- iterate (1+) 1, d <- idigits i ]   -- foldr (++) [] <~ idigits $ ()
problem40 = (fold (*) 1 ds, ds) where ds = (map (\n -> head (drop (n-1) irrafrac)) [1,10,100,1000, 10_000, 100_000, 1_000_000])

{--
    What is the largest n-digit pandigital prime that exists?
    
    It can't be 8 or 9 digits long, so we can start at 7
    7652413
    boxes: 85300, evals: 847735 (nat 14%, alg 0%, lazy 12%, re 72%)  runtime 0.137 sec.
-}
--problem41 = fold max 0 <~ head <~ dropWhile null <~ map (filter intIsPrime <~ map (ds2i 0)) <~ map (permutations <~ (1..)) <~ reverse $ 1..7
problem41 = fold max 0 
            • head 
            • dropWhile null 
            • map (filter intIsPrime • map (ds2i 0) • permutations • (1 `enumFromTo`)) 
            • reverse $ [1..7]

{--
    The nth term of the sequence of triangle numbers is given by, tn = �n(n+1); 
    so the first ten triangle numbers are:

    1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

    By converting each letter in a word to a number corresponding to its alphabetical position 
    and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. 
    If the word value is a triangle number then we shall call the word a triangle word.

    Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly 
    two-thousand common English words, how many are triangle words?
-}
problem42 file = withFile result file where
        result = (length  • filter triangleWord • map extract • ´,\s*´.splitted • fold (++) "")
        wordval str = isum [ ord c - ord 'A' + 1 | c <- unpacked str ]
        extract (m ~ ´"(\w+)"´) = unJust (m.group 1)
        extract _ = ""
        triangleWord str = head (dropWhile (< wv ) itriangles) == wv where wv = wordval str

withFile p file = do
    br <- openReader file
    lines <- br.getLines
    return (p lines)
    
{--
    The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the 
    digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

    Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

    d2d3d4=406 is divisible by 2 
    d3d4d5=063 is divisible by 3 
    d4d5d6=635 is divisible by 5 
    d5d6d7=357 is divisible by 7 
    d6d7d8=572 is divisible by 11 
    d7d8d9=728 is divisible by 13 
    d8d9d10=289 is divisible by 17 
    Find the sum of all 0 to 9 pandigital numbers with this property
-}
problem43 = (sum . map ds2in {-<~ filter property-}) [ [d1,d2,d3,d4,d5,d6,d7,d8,d9,d0] |
        !d1 <- from1to9,
        !d2 <- from0to9, d2 != d1,
        !d3 <- from0to9, d3 != d1 && d3 != d2,
        !d4 <- even, d4 != d3 && d4 != d2 && d4 != d1,
        !d5 <- from0to9, d5 != d4 && d5 != d3 && d5 != d2 && d5 != d1,
        (d3*100 + d4*10 + d5) `rem` 3 == 0,
        !d6 <- fünfer, d6 != d5 && d6  != d4 && d6 != d3 && d6 != d2 && d6 != d1,
        !d7 <- from0to9, d7 != d6 && d7 != d5 && d7  != d4 && d7 != d3 && d7 != d2 && d7 != d1,
        (d5*100 + d6*10 + d7) `rem` 7 == 0,
        !d8 <- from0to9, d8 != d7 && d8 != d6 && d8 != d5 && d8  != d4 && d8 != d3 && d8 != d2 && d8 != d1,
        (d6*100 + d7*10 + d8) `rem` 11 == 0,
        !d9 <- from0to9, d9 != d8 && d9 != d7 && d9 != d6 && d9 != d5 && d9  != d4 && d9 != d3 && d9 != d2 && d9 != d1,
        (d7*100 + d8*10 + d9) `rem` 13 == 0,
        !d0 <- from0to9, d0 != d9 && d0 != d8 && d0 != d7 && d0 != d6 && d0 != d5 && d0 != d4 && d0 != d3 && d0 != d2 && d0 != d1,
        (d8*100 + d9*10 + d0) `rem` 17 == 0]
    where
        from1to9 =  [1..9]
        from0to9 = [0..9]
        even = [0,2,4,6,8]
        fünfer = [0,5]
        {-
        property (d1:d2:d3:d4:d5:d6:d7:d8:d9:d0:[]) = 
            d4 `.&.` 1 == 0          -- divisible by 2
            && (d3*100 + d4*10 + d5) `rem` 3 == 0
            && (d6 == 0 || d6 == 5)   -- divisible by 5
            && (d5*100 + d6*10 + d7) `rem` 7 == 0
            && (d6*100 + d7*10 + d8) `rem` 11 == 0
            && (d7*100 + d8*10 + d9) `rem` 13 == 0
            && (d8*100 + d9*10 + d0) `rem` 17 == 0 -}

{--
    Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2. 
    The first ten pentagonal numbers are:

    1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

    It can be seen that P4 + P7 = 22 + 70 = 92 = P8. 
    However, their difference, 70 - 22 = 48, is not pentagonal.

    Find the pair of pentagonal numbers, Pj and Pk, 
    for which their sum and difference is pentagonal 
    and D = |Pk - Pj| is minimised; what is the value of D?
-}


ipentagonals = map (\n -> n*(3*n - 1) `quot` 2) [1 .. 50000]
-- pset = fold setBit 0n ipentagonals
    
-- isPentagonal n = n == head (dropWhile (<n) pentagonals)
seqElem n seq = n == head (dropWhile (<n) seq)

problem44 n = take n [ (pk, pj, pk - pj)  |
                pk <- ipentagonals,
                pj <- takeWhile (<pk) ipentagonals,
                isPentagonal (pk - pj),
                isPentagonal (pk + pj) 
               ]
    where
        ptree = TM.fromList (zip ipentagonals (repeat true))
        isPentagonal n = case lookup n ptree  of
            Just _  -> true
            Nothing -> false

    
{--
    Hexagonal   Hn=n(2n-1)   1, 6, 15, 28, 45, ... 

    It can be verified that T285 = P165 = H143 = 40755.

    Find the next triangle number that is also pentagonal and hexagonal.
-}
hexagonals = map (\a -> a * (2n*a - 1n)) (iterate (1N+) 1N)
pentagonals = map (\a -> a*(3n*a - 1n) `quot` 2n) (iterate (1N+) 1N)
problem45 = take3 (dropUntil (>40755n) triangles) (dropUntil (>40755n) pentagonals) (dropUntil (>40755n) hexagonals)
    where
        take3 :: [Integer] -> [Integer] -> [Integer] -> Integer
        take3 (xa@a:as) (xb@b:bs) (xc@c:cs)
            | a == b, b == c = a
            | otherwise = take3 (if a < m then as else xa) (if b < m then bs else xb) (if c < m then cs else xc)
            where m = max a  (max b c)
        take3 _ _ _ = undefined


{--
    It was proposed by Christian Goldbach that every odd composite number 
    can be written as the sum of a prime and twice a square.

    9 = 7 + 2*1²
    15 = 7 + 2*2²
    21 = 3 + 2*3²
    25 = 7 + 2*3²
    27 = 19 + 2*2²
    33 = 31 + 2*1²

    It turns out that the conjecture was false.

    What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?
-}
-- pure native sqrt java.lang.Math.sqrt :: Double -> Double
pure native doubleValue :: Integer -> Double
problem46 n = (take n . filter ((!) . goldbach)) oddNonPrimes
    where
        -- odd numbers that are not prime, and are not p+2 or p+4
        oddNonPrimes = loop (tail primes) where
            loop (p1:(ps@p2:_)) = let nonprimes = takeWhile (<p2) (iterate (2n+) (p1+6n)) -- p1+2 and p1+4 are goldbach
                                    in if null nonprimes then loop ps else nonprimes ++ loop ps
            loop _ = undefined
        -- goldbach c is true if there exists a double square q such that c-q is prime
        doubleSquares = map (\a -> 2n * a * a) (iterate (1n+) 1n)
        goldbach c = loop c doubleSquares where
            loop c (q:qs) | c <= q = false
                          | isprime (c-q) = true
                          | otherwise = loop c qs
            loop c [] = undefined
        -- we can assume that n is odd composite and not p+2 or p+4
        -- goldbachSlow n = gbWith n primes
        -- is (n-p)/2 a square
        {-
        gbWith n (p:ps)
            | n <= p = false
            | sq2 `rem` 2n == 0n, issquare (sq2 `div` 2n) = true
            | otherwise = gbWith n ps
            where sq2 = n - p -}
        -- issquare n = let d = doubleValue n; r = sqrt d in r.floor < r

{--
    The first two consecutive numbers to have two distinct prime factors are:

    14 = 2  7
    15 = 3  5

    The first three consecutive numbers to have three distinct prime factors are:

    644 = 2  7  23
    645 = 3  5  43
    646 = 2  17 19.

    Find the first four consecutive integers to have four distinct primes factors. 
    What is the first of these numbers?
-}
-- distinct as bs = all (`notElem` bs) as && all (`notElem` as) bs
problem47 n = head . consecutive (max n 1) . filter (hasUPrimeFactors n) $ (iterate (1n+) 210n)   -- 2*3*5*7
    where hasUPrimeFactors k n = (length . uniq . primefactors) n  == k
          consecutive k as = let init = take k as
                                 con a b = succ a == b
                                 rels (a:b:xs) = con a b && rels (b:xs)
                                 rels _ = true
                             in if rels init then init:consecutive k (tail as) else consecutive k (tail as)

{--
    The series, 1^1 + 2^2 + 3^3 + ... + 10^10 = 10405071317.
    Find the last ten digits of the series, 1^1 + 2^2 + 3^3 + ... + 1000^1000.
-}
problem48 n = (`mod` 10_000_000_000n) . sum . map (\i -> toInteger i `exp` i) $ [1..n]

{--
    The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, 
    is unusual in two ways: 
    (i) each of the three terms are prime, and, 
    (ii) each of the 4-digit numbers are permutations of one another.

    There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, 
    exhibiting this property, but there is one other 4-digit increasing sequence.

    What 12-digit number do you form by concatenating the three terms in this sequence?

-}
problem49 = show3 . head . concat . map property $   -- <~ filter ((4==) <~ length) <~ powerSet $ (0..9)  // wrong!! 
        [ [a,b,c,d] | a <- [0..9], b <- [0..9], c <- [0..9], d <- [0..9] ]
    where 
        show3 (a,b,c) = show a ++ show b ++ show c
        concat xs = [ x | ys <- xs, x <- ys ]
        property digits = [ (a,b,c) | 
                                a <- numbers, a > 999,
                                a != 1487,              -- exclude other result
                                b <- numbers, b > a,
                                c <- numbers, c > b,
                                c-b == b-a ] 
            where
                numbers = (filter intIsPrime . map (ds2i 0) . permutations) digits

{--
    The prime 41, can be written as the sum of six consecutive primes:

    41 = 2 + 3 + 5 + 7 + 11 + 13
    
    This is the longest sum of consecutive primes that adds to a prime below one-hundred.

    The longest sum of consecutive primes below one-thousand that adds to a prime, 
    contains 21 terms, and is equal to 953.

    Which prime, below one-million, can be written as the sum of the most consecutive primes?
-}
problem50Slow million = fold maxSndLength (0, []) . map writtenAsSum . takeWhile (<million) $ iprimes
    where
        maxSndLength a b = if length (snd a) > length (snd b) then a else b
        writtenAsSum p = loop p (takeWhile (<p) iprimes) 
          where
            loop p [] = (p, [])
            loop p ps | head ps >= p = (p, []) 
                      | n <- terms p ps, n > 0 = (p,take n ps)
                      | otherwise = loop p (tail ps)
            terms p ps = issum p ps 0 0
            issum n (p:ps) k t
                | k+p == n = t+1
                | k+p >  n = 0
                | otherwise = issum n ps (p+k) (t+1)
            issum n [] k t = 0

-- different approach, as runtime complexity is too steep exponential:
-- 1000        0.313 s
-- 2000        0.892 s
-- 4000        2.908 s
-- 8000        9.891 s
--16000        30 s        estimated
--   32k        1.5 min
--   64k        4.5min
--  128k        15min
--  256k        45min
--  512k        1.5h
--  1000000     4.5h (!!!!)
--  the new function runs in 13 secs.
problem50 n = fold maxFst (0,0) [ y | xs <- t4, y <- xs ]
    where
        from1 = iterate (1+) 1
        -- this gives 74498 lists for n=1_000_000, computed in just 3.4 seconds
        tails = takeUntil null . map (takeWhile (<n)) .  iterate tail $ iprimes -- [[2,3,5,7,...], [3,5,7,11...], [5,7,11,...], ....]  //(takeWhile (<million) iprimes)
        tailsums xs = loop xs 0 where
            loop [] acc = []
            loop (x:xs) acc | acc < n = x+acc : loop  xs (x+acc)
                            | otherwise = []
        t2  = map (filter (<n) . tailsums) tails
        t3  = map (zip from1) t2
        t4  = map (filter (intIsPrime . snd)) t3
        maxFst a b = if (fst a) > (fst b) then a else b

{--
    By replacing the 1st digit of *57, it turns out that six of the possible values: 
    157, 257, 457, 557, 757, and 857, are all prime.

    By replacing the 3rd and 4th digits of 56**3 with the same digit, 
    this 5-digit number is the first example having seven primes, yielding the family: 
    56003, 56113, 56333, 56443, 56663, 56773, and 56993. 
    Consequently 56003, being the first member of this family, 
    is the smallest prime with this property.

    Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) 
    with the same digit, is part of an eight prime value family.
-}
problem51 n = head . filter ((n==) . length) . family . head . filter (any (n==) .  map length . family) $ iprimes
-- list of lists all prime numbers that can be made from n by replacing k (1 to length n) digits
-- boxes: 684878558, evals: 3330300605 (nat 27%, alg 9%, lazy 24%, re 37%)  runtime 385.589 sec.
-- boxes:  63351666, evals:  351566748 (nat 23%, alg 8%, lazy 21%, re 45%)  runtime  37.88 sec.
    where 
      pss = map (filter ((0!=) . length) . powerSet . (1 `enumFromTo`))  $ [1..9]
      family n = filter ((!) . null) . map (rep dn) $ ps  
        where
            dn = idigits n
            ps = head . drop (length dn - 1) $ pss
            rep xs ps = filter intIsPrime 
                            . map (ds2i 0) 
                            . filter ((0!=) . head) 
                            . map (loop xs 1 ps) $ [0..9]
                where
                    -- loop z 1 _ 0  = [0]
                    loop z i [] d = z
                    loop (z:zs) i (j:js) d
                        | i == j = d : loop zs (i+1) js d
                        | otherwise = z : loop zs (i+1) (j:js) d
                    loop _ _ _ _  = []

{--
    It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, 
    but in a different order.

    Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.
-}
problem52 = (head . filter property . iterate succ) 1n
    where
        digitset :: Integer -> Int
        digitset n = fold withBit 0 (ndigits n)
        withBit n i = n  .|. (1 `shiftL` Integer.int i)
        property :: Integer -> Bool
        property n = all (digitset n ==) . map (digitset . (n*)) $ [2n, 3n, 4n, 5n, 6n]

{--
    There are exactly ten ways of selecting three from five, 12345:

    123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

    In combinatorics, we use the notation, 5C3 = 10.

    In general,

    nCr =  n! / r!(n-r)! ,where r <= n, n! = n(n1)...321, and 0! = 1. 

    It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

    How many, not necessarily distinct, values of  nCr, for 1  n  100, are greater than one-million?
-}
problem53 limit = length . filter (>1_000_000n) $ [ n `nCr` r | n <- [1n .. toInteger limit], r <- [1n .. (n-1n)] ]
    where nCr n r = fac n `div` (fac r * fac (n-r))
          fac n = prod [1.toInteger .. n]


{--
    If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

    Not all numbers produce palindromes so quickly. For example,

    349 + 943 = 1292,
    1292 + 2921 = 4213
    4213 + 3124 = 7337

    That is, 349 took three iterations to arrive at a palindrome.

    Although no one has proved it yet, it is thought that some numbers, like 196, never produce a palindrome. 
    A number that never forms a palindrome through the reverse and add process is called a Lychrel number. 
    Due to the theoretical nature of these numbers, and for the purpose of this problem, 
    we shall assume that a number is Lychrel until proven otherwise. 
    In addition you are given that for every number below ten-thousand, it will either 
    (i) become a palindrome in less than fifty iterations, or, 
    (ii) no one, with all the computing power that exists, has managed so far to map it to a palindrome. 
    
    In fact, 10677 is the first number to be shown to require over fifty iterations before producing a palindrome: 
    4668731596684224866951378664 (53 iterations, 28-digits).

    Surprisingly, there are palindromic numbers that are themselves Lychrel numbers; the first example is 4994.

    How many Lychrel numbers are there below ten-thousand?
-}
problem55 limit = length . filter lychrel $ [1n .. toInteger limit]
    where
        -- a number is lychrel for the purpose of this problem, 
        -- if it does not yield a palindrome in 50 steps
        lychrel n = (!) . any (palindrome . show) . take 50 . tail . iterate revadd $ n
        revadd n = n + (ds2n . reverse . ndigits) n 

{--
    A googol (10^100) is a massive number: one followed by one-hundred zeros; 100^100 is almost 
    unimaginably large: one followed by two-hundred zeros. 
    Despite their size, the sum of the digits in each number is only 1.

    Considering natural numbers of the form, a^b, where a, b < 100, what is the maximum digital sum?
-}
problem56 = fold max 0n [ (sum . ndigits . exp n) i | n <- [1n .. 99n], i <- [50..99] ]

{--
    It is possible to show that the square root of two can be expressed as an infinite continued fraction.

    2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

    By expanding this for the first four iterations, we get:

    1 + 1/2 = 3/2 = 1.5                                      1/2
    1 + 1/(2 + 1/2) = 7/5 = 1.4                              2/5
    1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...             5/12
    1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...    12/29


    The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, 
    is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

    In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

-}
problem57 = length . filter property . map ((1n,1n) `rplus`) . take 1000 . iterate next $ (1n,2n)
    where next (nom, denom) = (denom, denom+denom+nom)
          property (nom, denom) = length (ndigits nom) > length (ndigits denom)
-- boxes: 1162285, evals: 1591461 (nat 49%, alg 24%, lazy 25%, re 1%)  runtime 0.744 sec.          

{--
   Each character on a computer is assigned a unique code and the preferred standard is ASCII 
   (American Standard Code for Information Interchange). 
   For example, uppercase A = 65, asterisk (*) = 42, and lowercase k = 107.

    A modern encryption method is to take a text file, convert the bytes to ASCII, 
    then XOR each byte with a given value, taken from a secret key. 
    The advantage with the XOR function is that using the same encryption key on the cipher text, 
    restores the plain text; for example, 65 XOR 42 = 107, then 107 XOR 42 = 65.

    For unbreakable encryption, the key is the same length as the plain text message, 
    and the key is made up of random bytes. The user would keep the encrypted message 
    and the encryption key in different locations, and without both "halves", it is 
    impossible to decrypt the message.

    Unfortunately, this method is impractical for most users, so the modified method 
    is to use a password as a key. If the password is shorter than the message, 
    which is likely, the key is repeated cyclically throughout the message. 
    The balance for this method is using a sufficiently long password key for security, 
    but short enough to be memorable.

    Your task has been made easy, 
    as the encryption key consists of three lower case characters. 
    Using cipher1.txt (right click and 'Save Link/Target As...'), a file containing 
    the encrypted ASCII codes, and the knowledge that the plain text must contain 
    common English words, decrypt the message and find the sum of the ASCII values in the original text.
-}
message = [
    79,59,12,2,79,35,8,28,20,2,3,68,8,9,68,45,0,12,9,67,68,4,7,5,23,27,1,21,
    79,85,78,79,85,71,38,10,71,27,12,2,79,6,2,8,13,9,1,13,9,8,68,19,7,1,71,56,
    11,21,11,68,6,3,22,2,14,0,30,79,1,31,6,23,19,10,0,73,79,44,2,79,19,6,28,68,
    16,6,16,15,79,35,8,11,72,71,14,10,3,79,12,2,79,19,6,28,68,32,0,0,73,79,86,
    71,39,1,71,24,5,20,79,13,9,79,16,15,10,68,5,10,3,14,1,10,14,1,3,71,24,13,19,
    7,68,32,0,0,73,79,87,71,39,1,71,12,22,2,14,16,2,11,68,2,25,1,21,22,16,15,6,10,
    0,79,16,15,10,22,2,79,13,20,65,68,41,0,16,15,6,10,0,79,1,31,6,23,19,28,68,19,7,
    5,19,79,12,2,79,0,14,11,10,64,27,68,10,14,15,2,65,68,83,79,40,14,9,1,71,6,16,20,
    10,8,1,79,19,6,28,68,14,1,68,15,6,9,75,79,5,9,11,68,19,7,13,20,79,8,14,9,1,71,
    8,13,17,10,23,71,3,13,0,7,16,71,27,11,71,10,18,2,29,29,8,1,1,73,79,81,71,59,12,
    2,79,8,14,8,12,19,79,23,15,6,10,2,28,68,19,7,22,8,26,3,15,79,16,15,10,68,3,14,22,12,
    1,1,20,28,72,71,14,10,3,79,16,15,10,68,3,14,22,12,1,1,20,28,68,4,14,10,71,1,
    1,17,10,22,71,10,28,19,6,10,0,26,13,20,7,68,14,27,74,71,89,68,32,0,0,71,28,1,
    9,27,68,45,0,12,9,79,16,15,10,68,37,14,20,19,6,23,19,79,83,71,27,11,71,27,1,11,
    3,68,2,25,1,21,22,11,9,10,68,6,13,11,18,27,68,19,7,1,71,3,13,0,7,16,71,28,11,71,
    27,12,6,27,68,2,25,1,21,22,11,9,10,68,10,6,3,15,27,68,5,10,8,14,10,18,2,79,6,2,12,
    5,18,28,1,71,0,2,71,7,13,20,79,16,2,28,16,14,2,11,9,22,74,71,87,68,45,0,12,9,79,12,
    14,2,23,2,3,2,71,24,5,20,79,10,8,27,68,19,7,1,71,3,13,0,7,16,92,79,12,2,79,19,6,28,
    68,8,1,8,30,79,5,71,24,13,19,1,1,20,28,68,19,0,68,19,7,1,71,3,13,0,7,16,73,79,93,71,
    59,12,2,79,11,9,10,68,16,7,11,71,6,23,71,27,12,2,79,16,21,26,1,71,3,13,0,7,16,75,79,
    19,15,0,68,0,6,18,2,28,68,11,6,3,15,27,68,19,0,68,2,25,1,21,22,11,9,10,72,71,24,5,20,
    79,3,8,6,10,0,79,16,8,79,7,8,2,1,71,6,10,19,0,68,19,7,1,71,24,11,21,3,0,73,79,85,87,
    79,38,18,27,68,6,3,16,15,0,17,0,7,68,19,7,1,71,24,11,21,3,0,71,24,5,20,79,9,6,11,1,
    71,27,12,21,0,17,0,7,68,15,6,9,75,79,16,15,10,68,16,0,22,11,11,68,3,6,0,9,72,16,71,
    29,1,4,0,3,9,6,30,2,79,12,14,2,68,16,7,1,9,79,12,2,79,7,6,2,1,73,79,85,86,79,33,17,
    10,10,71,6,10,71,7,13,20,79,11,16,1,68,11,14,10,3,79,5,9,11,68,6,2,11,9,8,68,15,6,
    23,71,0,19,9,79,20,2,0,20,11,10,72,71,7,1,71,24,5,20,79,10,8,27,68,6,12,7,2,31,16,
    2,11,74,71,94,86,71,45,17,19,79,16,8,79,5,11,3,68,16,7,11,71,13,1,11,6,1,17,10,0,
    71,7,13,10,79,5,9,11,68,6,12,7,2,31,16,2,11,68,15,6,9,75,79,12,2,79,3,6,25,1,71,27,
    12,2,79,22,14,8,12,19,79,16,8,79,6,2,12,11,10,10,68,4,7,13,11,11,22,2,1,68,8,9,68,
    32,0,0,73,79,85,84,79,48,15,10,29,71,14,22,2,79,22,2,13,11,21,1,69,71,59,12,14,28,
    68,14,28,68,9,0,16,71,14,68,23,7,29,20,6,7,6,3,68,5,6,22,19,7,68,21,10,23,18,3,16,
    14,1,3,71,9,22,8,2,68,15,26,9,6,1,68,23,14,23,20,6,11,9,79,11,21,79,20,11,14,10,75,
    79,16,15,6,23,71,29,1,5,6,22,19,7,68,4,0,9,2,28,68,1,29,11,10,79,35,8,11,74,86,91,68,
    52,0,68,19,7,1,71,56,11,21,11,68,5,10,7,6,2,1,71,7,17,10,14,10,71,14,10,3,79,8,14,
    25,1,3,79,12,2,29,1,71,0,10,71,10,5,21,27,12,71,14,9,8,1,3,71,26,23,73,79,44,2,79,
    19,6,28,68,1,26,8,11,79,11,1,79,17,9,9,5,14,3,13,9,8,68,11,0,18,2,79,5,9,11,68,1,
    14,13,19,7,2,18,3,10,2,28,23,73,79,37,9,11,68,16,10,68,15,14,18,2,79,23,2,10,10,
    71,7,13,20,79,3,11,0,22,30,67,68,19,7,1,71,8,8,8,29,29,71,0,2,71,27,12,2,79,11,9,3,
    29,71,60,11,9,79,11,1,79,16,15,10,68,33,14,16,15,10,22,73
    ]


problem59 = result . head . filter hasWords . map (decrypt (take 32 message)) $ keys
    where
        result (_, key, _) = decrypt message key
        decrypt msg key = (stringy clear, key, fold (+) 0 clear) where
            clear = zipWith (`xor`) msg (cycle key)
        stringy :: [Int] -> String
        stringy is = fold (++) "" . map (ctos . chr) $ is
        hasWords (´\b[Tt]he\b´, _, _) = true
        hasWords _ = false
        keys = [ [a,b,c] | a <- [ord 'a' .. ord 'z'], 
                           b <- [ord 'a' .. ord 'z'], 
                           c <- [ord 'a' .. ord 'z']]
        
-- boxes: 599568, evals: 2909118 (nat 15%, alg 9%, lazy 44%, re 30%)  runtime 1.107 sec.
-- Rang 246 (Germany)


{--
    The primes 3, 7, 109, and 673, are quite remarkable. 
    By taking any two primes and concatenating them in any order the result will always be prime. 
    For example, taking 7 and 109, both 7109 and 1097 are prime. 
    The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

    Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.
-}
derive Show (a,b,c,d,e,f)
problem60 = head [ (a,b,c,d,e, a+b+c+d+e) | 
                    a <- tail iprimes,
                    b <- takeWhile (<a) (tail iprimes),
                    ok b a,
                    c <- takeWhile (<b) (tail iprimes),
                    ok c a, ok c b,
                    d <- takeWhile (<c) (tail iprimes),
                    ok d a, ok d b, ok d c,
                    e <- takeWhile (<d) (tail iprimes),
                    ok e a, ok e b, ok e c, ok e d]
    where
        shift n = loop n 10
            where
                loop n x0 = if n < x0 then x0 else loop n (10*x0)
        -- okx a b = isJust (lookup pairTree (b*shift a + a))
        ok a b = intIsPrime (a*shift b+b) && intIsPrime (b*shift a+a)
-- (8389, 6733, 5701, 5197, 13, 26033)
-- boxes: 86646191, evals: 1412745677 (nat 6%, alg 3%, lazy 5%, re 83%)  runtime 140.249 sec.
-- (8389, 6733, 5701, 5197, 13, 26033)
-- boxes: 27265122, evals: 1201401695 (nat 1%, alg 0%, lazy 1%, re 96%)  runtime 89.678 sec.
-- Rang 236

{--
    Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) 
    numbers and are generated by the following formulae:

    Triangle    P3,n=n(n+1)/2   1, 3, 6, 10, 15, ... 
    Square      P4,n=n^2        1, 4, 9, 16, 25, ... 
    Pentagonal  P5,n=n(3n-1)/2  1, 5, 12, 22, 35, ... 
    Hexagonal   P6,n=n(2n-1)    1, 6, 15, 28, 45, ... 
    Heptagonal  P7,n=n(5n-3)/2  1, 7, 18, 34, 55, ... 
    Octagonal   P8,n=n(3n-2)    1, 8, 21, 40, 65, ... 
    
    The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.
    
    The set is cyclic, in that the last two digits of each number is the first two digits of the next number 
    (including the last number with the first). 
    Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882), 
    is represented by a different number in the set. 
    This is the only set of 4-digit numbers with this property. 
    
    Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, 
    square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.
-}
derive Show (a,b,c,d,e,f,g)
problem61 = head [ (a,b,c,d,e,f, a+b+c+d+e+f) | [as,bs,cs,ds,es,fs] <- config,
                        a <- as,
                        b <- filter (cyc a) bs,
                        c <- filter (cyc b) cs,
                        d <- filter (cyc c) ds,
                        e <- filter (cyc d) es,
                        f <- filter (cyc e) . filter (`cyc` a) $ fs ]
    where
        config = permutations [fd tris, fd sqrs, fd pens, fd hexs, fd heps, fd octs]
        nums = iterate succ 1
        fd = takeWhile (<10_000) . dropWhile (<1_000)      -- select 4 digit numbers
        tris = map (\n -> n*(n+1) `div` 2) nums
        sqrs = map (\n -> n*n)             nums
        pens = map (\n -> n*(3*n-1) `div` 2) nums
        hexs = map (\n -> n*(2*n-1)) nums
        heps = map (\n -> n*(5*n-3) `div` 2) nums
        octs = map (\n -> n*(3*n-2)) nums
        -- last two digits of a is first two of b
        cyc a b = (a `rem` 100) == (b `div` 100)

-- (8128, 2882, 8256, 5625, 2512, 1281, 28684)
-- boxes: 397878, evals: 1631360 (nat 0%, alg 0%, lazy 26%, re 73%)  runtime 1.313 sec.
-- Rang: 230            

{--
    The cube, 41063625 (345^3), can be permuted to produce two other cubes: 
    56623104 (384^3) and 66430125 (405^3). In fact, 41063625 is the smallest cube 
    which has exactly three permutations of its digits which are also cube.

    Find the smallest cube for which exactly five permutations of its digits are cube.
-}
problem62 n = lookup ((head . head) solutions) cubset 
    where
        numSet n = fold (++) "" . map Long.show . sortBy (flip (<=>)) . ldigits $ n
        cubes = map (\n -> n*n*n) (iterate succ 1L)     -- Kubikzahlen
        numcbs = map numSet (take 10000 cubes)  -- Ziffernsets der Kubikzahlen
        solutions = filter ((n==) . length) . group . sort $ numcbs
        cubset = TM.fromList (zip numcbs cubes)
        group [] = []
        group [x] = [[x]]
        group (xs@x:_) = takeWhile (x==) xs : group (dropWhile (x==) xs)  
        
        
               
zeroNotFirst (0l:_) = false
zeroNotFirst _      = true
cubeSet = uniq . sort . filter isCube . map ds2l  . filter zeroNotFirst . permutations . ldigits        
isCube n | n > 10L = loop 0L (n `div` 8L) (n `div` 4L)
    where
        loop a b c -- debug = undefined
           | b3 == n = true
           | a >=  c = false
           | a >=  b = false
           | b3 >  n || b3 < b = loop a ((a+b) `div` 2L) b
           | otherwise  = loop b ((b+c) `div` 2L) c
           where b3 = b*b*b
                 -- debug = do stderr << "loop a=" << a << ", b=" << b << ", c=" << c << ", b^3=" << b3 << ", n=" << n << "\n" 
            
isCube 8L = true
isCube 1L = true
isCube _  = false

{--
    The 5-digit number, 16807=7^5, is also a fifth power. 
    Similarly, the 9-digit number, 134217728=8^9, is a ninth power.

    How many n-digit positive integers exist which are also an nth power?
-}
-- we need to consider only 3 to 9, take powers until number of digits is lower than exponent
problem63 = zip [ (base, e, power) | base <- [1n .. 9n],
                  e    <- takeUntil (\e -> length (ndigits (base `exp` e)) < e) (iterate succ 1),
                  power = base `exp` e,
                  length (ndigits power) == e 
                ] (iterate succ 1)
-- boxes: 3841, evals: 6488 (nat 48%, alg 13%, lazy 29%, re 8%)  runtime 0.027 sec.
-- Rang: 211

{--
    The square root of 2 can be written as an infinite continued fraction
     sqrt(2) = 1 + (1/2+ (1/ 2+(1/ 2 + ...)
     
    The infinite continued fraction can be written, 2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. 
    In a similar way, 23 = [4;(1,3,1,8)].
    
    Hence the sequence of the first ten convergents for 2 are:

    1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...
    
    What is most surprising is that the important mathematical constant,
    e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].

    The first ten terms in the sequence of convergents for e are:

    2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...
    The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

    Find the sum of digits in the numerator of the 100th convergent of the 
    continued fraction for e.
-}

data ContinuedFraction a = CF Integer (a -> [Integer])  a
sqrt2 = CF 1n cycle   [2n]
e     = CF 2n concat  [[1n, a+a, 1n] | a <- (iterate succ 1n)] 
approx n (CF ni f fs) = (ni, 1n) `rplus` fraction (take n (f fs))
    where 
        fraction []  = (0n, 1n)
        fraction [x] = (1n, x)
        fraction (x:xs) = case (x,1n) `rplus` fraction xs of (a,b) -> (b,a)


problem65 = sum . ndigits . fst $ a -- ("sqrt:", map (`approx` sqrt2)  (1..10), "e:", map (`approx` e)  (1..10))
    where a = approx 99 e
-- boxes: 1331, evals: 4640 (nat 22%, alg 9%, lazy 37%, re 30%)  runtime 0.014 sec.

{--
    All square roots are periodic when written as continued fractions and can be written in the form:
    sqrt N = a0 + (1 / a1 + (1 / a2 + (1 / a3 + ...)))
    
    For example, let us consider 23:

    sqrt 23 = 4 +  sqrt 23 - 4 = 4 + 1 / (1 / sqrt 23 - 4) [1,2565...]= 4 + 1 / (1 + (sqrt 23 - 3) / 7) [1,2565... indeed]
    
    The process can be summarised as follows:
    
    ...
    
    It can be seen that the sequence is repeating. 
    For conciseness, we use the notation 23 = [4;(1,3,1,8)], 
    to indicate that the block (1,3,1,8) repeats indefinitely.
    
    The first ten continued fraction representations of (irrational) square roots are:

    sqrt 2=[1;(2)], period=1
    sqrt 3=[1;(1,2)], period=2
    sqrt 5=[2;(4)], period=1
    sqrt 6=[2;(2,4)], period=2
    sqrt 7=[2;(1,1,1,4)], period=4
    sqrt 8=[2;(1,4)], period=2
    sqrt 10=[3;(6)], period=1
    sqrt 11=[3;(3,6)], period=2
    sqrt 12= [3;(2,6)], period=2
    sqrt 13=[3;(1,1,1,1,6)], period=5
    
    Exactly four continued fractions, for N <= 13, have an odd period.
    
    How many continued fractions for N <= 10000 have an odd period?
    
-}        
problem64 limit = length . filter oddFrac . map fracSqrt $ [1n .. toInteger limit]
    where
        oddFrac (CF _ _ fs) = length fs `rem` 2 != 0
-- boxes: 4306080, evals: 18020139 (nat 27%, alg 8%, lazy 37%, re 27%)  runtime 6.143 sec.
-- Rang 200        

fracCF (CF _ _ fr) = fr

fracSqrt r = case isSquare r of
        Right n -> CF n id [] 
        Left a0 -> CF a0 cycle (findCyc (sqMinus r a0 a0 1n)) -- sqrt 23 = 4 + (sqrt 23 - 4) = 4 + 1 / ( 1 / (sqrt 23 -4))
    where
        findCyc (f1:fs) = map snd (f1 : takeUntil (f1==) fs)
        findCyc [] = []
        
-- sqMinus r sq p  computes the periodic fraction for  q / (sqrt r - p), 
-- where sq is the integer part of sqrt r, which is irrational
-- q / (sqrt r - p) = x / (sqrt r + p) where x = (r - p*p) / q
-- q / (sqrt r - p) = (sqrt r + p) / x
sqMinus r sq p q = let 
                    x = (r - p*p) `div` q         -- x = 23 - 16 = 7
                    a1 = (sq + p) `div` x         -- 4+4 / 7 == 1
                    -- next term is (sqrt r + p) / x - a1
                    -- = sqrt r / x + p / x - (x*a1) / x
                    -- = sqrt r + (p-x*a1) / x
                    p1 = (p - x*a1)             -- 4 - 7*1 ==  - 3
              in ((p, q), a1) : sqMinus r sq (negate p1) x
            
{--
    Consider quadratic Diophantine equations of the form:

    x^2 - Dy^2 = 1
    x^2 = 1 + D*y^2

    For example, when D=13, the minimal solution in x is 649^2 - 13*180^2 = 1.

    It can be assumed that there are no solutions in positive integers when D is square.

    By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

    3^2 - 2*2^2 = 1
    2^2 - 3*1^2 = 1
    9^2 - 5*4^2 = 1
    5^2 - 6*2^2 = 1
    8^2 - 7*3^2 = 1
    
    Hence, by considering minimal solutions in x for D <= 7, the largest x is obtained when D=5.
    
    Find the value of D <= 1000 in minimal solutions of x for which the largest value of x is obtained.
-}
{--
    (1) x^2 - Dy^2 = L
    Satz 13.1 Wenn |L| < sqrt D dann sind die Lösungen  x = Ak und
    y = Bk, wobei Ak/Bk ein Näherungsbruch von sqrt D ist.
    Es ist daher nur nötig, für x, y die verschiedenen Näherungszähler Ai und -nenner Bi von
    sqrt D einzusetzen und zuzusehen, ob einmal L herauskommt.
-}
problem66 limit = fold maxSnd (0n,0n) . map solve $ [1n .. toInteger limit]
    where
        maxSnd a b = if snd a > snd b then a else b
        solve d
            | Right _ <- isSquare d = (d, 0n)          -- no solution
            | otherwise = (d, fst . head $ solutions)
            where
                 fd = fracSqrt d
                 solutions = [ (x,y) | (x,y) <- map (flip approx fd) (iterate succ 1),
                                    x*x - d*y*y == 1n]
-- boxes: 1035030, evals: 6393461 (nat 21%, alg 7%, lazy 37%, re 33%)  runtime 1.311 sec.
-- Rang 189                                    

                        
                           

isSquare n | n > 10n = loop 0n (n `div` 4n) (n `div` 2n)
    where
        loop a b c -- debug = undefined
           | b2 == n = Right b
           | a >=  c = left b
           | a ==  b, b+1n == c = Left b
           | b2 >  n = loop a ((a+b) `div` 2n) b
           | otherwise = loop b ((b+c) `div` 2n) c
           where b2 = b*b
                 left b | b*b < n = Left b
                        | otherwise = left (b-1n)
            
isSquare 10n = Left 3n
isSquare 9n = Right 3n
isSquare 8n = Left  2n
isSquare 7n = Left  2n
isSquare 6n = Left  2n
isSquare 5n = Left  2n
isSquare 4n = Right 2n
isSquare 3n = Left  1n
isSquare 2n = Left  1n
isSquare 1n = Right 1n
isSquare _  = Right 0n

intIsSquare n | n > 10 = loop 0 (n `quot` 4) (n `quot` 2)
    where
        loop a b c -- debug = undefined
           | b2 == n = Right b
           | a >=  c = left b
           | a ==  b, b+1 == c = Left b
           | b2 >  n = loop a ((a+b) `div` 2) b
           | otherwise = loop b ((b+c) `div` 2) c
           where b2 = b*b
                 -- debug = do stderr << "loop a=" << a << ", b=" << b << ", c=" << c << ", b^2=" << b2 << ", n=" << n << "\n"
                 left b | b*b < n = Left b
                        | otherwise = left (b-1)
            
intIsSquare 10 = Left 3
intIsSquare 9 = Right 3
intIsSquare 8 = Left  2
intIsSquare 7 = Left  2
intIsSquare 6 = Left  2
intIsSquare 5 = Left  2
intIsSquare 4 = Right 2
intIsSquare 3 = Left  1
intIsSquare 2 = Left  1
intIsSquare 1 = Right 1
intIsSquare _ = Right 0

{--
    By starting at the top of the triangle below and moving to adjacent numbers on the row below, 
    the maximum total from top to bottom is 23.

       3
      7 5
     2 4 6
    8 5 9 3
    
    That is, 3 + 7 + 4 + 9 = 23.
    
    Find the maximum total from top to bottom in triangle.txt, 
    a 15K text file containing a triangle with one-hundred rows.
    
    NOTE: This is a much more difficult version of Problem 18. 
    It is not possible to try every route to solve this problem, as there are 2^99 altogether! 
    If you could check one trillion (10^12) routes every second it would take over twenty billion 
    years to check them all. There is an efficient algorithm to solve it. ;o)
-}
problem67 file = withFile problem file
        
    where
        problem trilines = maxsum (reverse triangle) 
            where
                check n (ns:nss)
                    | n == length ns = ns : check (n+1) nss
                    | otherwise = error ("bad triangle row " ++ show n)
                check n []
                    | n > 1 = []
                    | otherwise = error ("empty triangle")
                maxsum (al:au:as) = maxsum (an:as) where
                    an = zipWith (Int.+) ar au
                    ar = zipWith (Int.max) al (tail al)
                maxsum [[n]] = n
                maxsum bad = error ("bad triangle: " ++ show bad)    
                numlines = map (map atoi . ´\s+´.splitted) trilines
                triangle = check 1  numlines  
-- boxes: 41208, evals: 132917 (nat 23%, alg 0%, lazy 34%, re 41%)  runtime 0.106 sec.

{--
    Consider the following "magic" 3-gon ring, filled with the numbers 1 to 6, 
    and each line adding to nine.
    
         4
           3
         1   2   6
       5
    
    
    Working clockwise, and starting from the group of three with the numerically 
    lowest external node (4,3,2 in this example), each solution can be described uniquely. 
    For example, the above solution can be described by the set: 4,3,2; 6,2,1; 5,1,3.
    
    It is possible to complete the ring with four different totals: 9, 10, 11, and 12. 
    There are eight solutions in total.
    
    Total Solution Set 
    9   4,2,3; 5,3,1; 6,1,2 
    9   4,3,2; 6,2,1; 5,1,3 
    10  2,3,5; 4,5,1; 6,1,3 
    10  2,5,3; 6,3,1; 4,1,5 
    11  1,4,6; 3,6,2; 5,2,4 
    11  1,6,4; 5,4,2; 3,2,6 
    12  1,5,6; 2,6,4; 3,4,5 
    12  1,6,5; 3,5,4; 2,4,6 
    
    By concatenating each group it is possible to form 9-digit strings; 
    the maximum string for a 3-gon ring is 432621513.
    
    Using the numbers 1 to 10, and depending on arrangements, 
    it is possible to form 16- and 17-digit strings. 
    What is the maximum 16-digit string for a "magic" 5-gon ring?

                       a
                        \
                         b    d   
                       /  \  /
                     i      c
                    / \    /
                   j   g--e--f
                        \
                         h
-}                          
problem68 x5 =  reverse . uniq . sort . filter ((16==) . length) . map (fold (++) "" . map toStr . rotate) $ 
            [ [[a,b,c], [d,c,e], [f,e,g], [h,g,i], [j,i,b]] |
                a <- nums,
                b <- filter (a !=) nums,
                c <- filter (`notElem` [a,b])   nums,
                d <- filter (`notElem` [a,b,c]) nums,
                e <- filter (`notElem` [a,b,c,d]) nums,
                a+b+c == d+c+e,
                f <- filter (`notElem` [a,b,c,d,e]) nums,
                g <- filter (`notElem` [a,b,c,d,e,f]) nums,
                a+b+c == f+e+g,
                h <- filter (`notElem` [a,b,c,d,e,f,g]) nums,
                i <- filter (`notElem` [a,b,c,d,e,f,g,h]) nums,
                a+b+c == h+g+i,
                j <- filter (`notElem` [a,b,c,d,e,f,g,h,i]) nums,
                a+b+c == j+i+b
                 ] where
    nums = [1..10]
    rotate xs 
        | head (head xs) == minimum = xs
        | otherwise = rotate (tail xs ++ [head xs])
        where
            minimum = fold min 11 . map head $ xs
    toStr [a,b,c] = show a ++ show b ++ show c
    toStr _ = undefined
-- boxes: 1952531, evals: 9957092 (nat 53%, alg 17%, lazy 24%, re 3%)  runtime 1.204 sec.
-- Rang 175

{--
    Euler's Totient function, f(n) [sometimes called the phi function], 
    is used to determine the number of numbers less than n which are 
    relatively prime to n. 
    
    For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and 
    relatively prime to nine, f(9)=6.

    n Relatively Prime f(n) n/f(n) 
    2 1         1       2 
    3 1,2       2       1.5 
    4 1,3       2       2 
    5 1,2,3,4   4       1.25 
    6 1,5       2       3 
    7 1,2,3,4,5,6 6     1.1666... 
    8 1,3,5,7   4       2 
    9 1,2,4,5,7,8 6     1.5 
    10 1,3,7,9  4       2.5 
    
    It can be seen that n=6 produces a maximum n/f(n) for n <= 10.
    
    Find the value of n <= 1,000,000 for which n/f(n) is a maximum.
    
    Zwei natürliche Zahlen sind teilerfremd oder relativ prim, 
    wenn es keine natürliche Zahl außer der Eins gibt, die beide Zahlen teilt.
    
    Der Wert der eulerschen -Funktion lässt sich für jede Zahl aus ihrer 
    kanonischen Primfaktorzerlegung
        n = prod (p_i^k_p_i)
 
    berechnen:
        phi(n) = prod (p^(k_p-1)(p-1)
    Für Primzahlen gilt:
         phi(p) = p-1    
 
    Diese Formel folgt direkt aus der Multiplikativität der -Funktion und der 
    Formel für Primzahlpotenzen.

    Beispiel:
        phi(72) = phi(2^3 * 3^2) = 2^2 * (2-1) * 3^1 * (3-1) = 4*1*3*2 = 24

-}
problem69 limit = fold maxSnd (0, 0.0) . map nphi $ [2..limit] 
    where
        maxSnd a b = if snd a > snd b then a else b
        nphi :: Int -> (Int, Double)
        nphi n = (n, n.double / (phi n).double)
        
phi 1 = 1
phi n = iprod (map phi' (icanonicpfs n)) 
    where 
        phi' (p,k) = iexp p (k-1) * (p-1)
-- boxes: 57269134, evals: 234172962 (nat 26%, alg 7%, lazy 25%, re 40%)  runtime 32.044 sec.
-- Rang 165

{--
    Euler's Totient function, f(n) [sometimes called the phi function], is used to determine the number of 
    positive numbers less than or equal to n which are relatively prime to n. 
    For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, f(9)=6.
    The number 1 is considered to be relatively prime to every positive number, so f(1)=1. 

    Interestingly, f(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

    Find the value of n, 1 < n < 10^7, for which f(n) is a permutation of n and the ratio n/f(n) produces a minimum.
-}
problem70 limit = fold min3rd (0, 0, 9e99) -- <~ map nphi <~ filter permutes <~ zip numbers <~ map phi $ numbers 
    [ (n, pn, n.double/pn.double) |
        p1 <- reverse (takeWhile (((2*limit)>=) . sqr) iprimes),
        p2 <- reverse (takeWhile (p1>=) iprimes),
        n = p1*p2,
        n < limit,
        pn = (p1-1)*(p2-1), -- phi n,
        permutes n pn ]
    where
        sqr n = n*n
        min3rd (as@(_,_,a)) (bs@(_,_,b)) = if  a <  b then as else bs
        -- nphi :: (Int, Int) -> (Int, Int, Double)
        -- nphi (n, p) = (n, p, n.double / p.double)
        permutes a b = perm as bs -- all (`elem` bs) as && (all (`elem` as) bs && (as `elem` permutations bs))
            where
                as = idigits a
                bs = idigits b
                perm [a] [b] = a == b
                perm [a] _   = false
                perm  _  []  = false
                perm (a:as) bs = (a `elem` bs) && (perm as (takeWhile (a!=) bs ++ tail (dropWhile(a!=) bs)))
                perm [] _    = undefined
                
-- boxes: 984797568, evals: 4347826379 (nat 24%, alg 7%, lazy 21%, re 46%)  runtime 417.353 sec.
-- boxes:   7987318, evals:   25077529 (nat 29%, alg 15%, lazy 31%, re 24%) runtime   3.431 sec.
-- Rang 163            

{--
    Consider the fraction, n/d, where n and d are positive integers. 
    If n < d and HCF(n,d)=1, it is called a reduced proper fraction.

    If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

    1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

    It can be seen that 2/5 is the fraction immediately to the left of 3/7.

    By listing the set of reduced proper fractions for d <= 1,000,000 in ascending order of size, 
    find the numerator of the fraction immediately to the left of 3/7.
-}
problem71 limit = loop (1n, toInteger limit) (3n, 7n) 2n (toInteger limit)
    where
        loop min max n d
            | d <= 1n = min
            | n >= d  = loop min max n' (d - 1n)
            | rnd `rlt` max = if min `rlt` rnd then loop rnd max (n + 1n) d else loop min max (n + 1n) d
            | otherwise = loop min max n' (d - 1n)
            where rnd = reduced (n,d)
                  n' = fst min * (d - 1n) `div` snd min
-- boxes: 32910675, evals: 110959051 (nat 41%, alg 10%, lazy 27%, re 20%)  runtime 18.951 sec.                  

{--
    Consider the fraction, n/d, where n and d are positive integers. 
    If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

    If we list the set of reduced proper fractions for d = 8 in ascending order of size, we get:

    1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
    1/8, 3/8, 5/8, 7/8, 1/7, 2/7, 3/7, 4/7, 5/7, 6/7, 1/6, 5/6, 1/5, 2/5, 3/5, 4/5, 1/4, 3/4, 1/3, 2/3, 1/2

    It can be seen that there are 21 elements in this set.

    How many elements would be contained in the set of reduced proper fractions for d  1,000,000?
-}

problem72 limit = sum . map toInteger . map phi $ [2 .. limit]  
-- boxes: 55269143, evals: 224172920 (nat 26%, alg 7%, lazy 25%, re 41%)  runtime 32.622 sec.
-- Rang 151

{--
    Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, 
    it is called a reduced proper fraction.

    If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:

    1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

    It can be seen that there are 3 fractions between 1/3 and 1/2.

    How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d <= 10,000?
-}
problem73 limit = length  [ (n, d) |  d <- [2 .. limit],
                    -- sn = fst min * d `div` snd min,
                    n <- [d `div` 3 .. d `div` 2],
                    igcd n d == 1,                     -- (n, d),
                    n*2 < d,
                    d   < 3*n]
                    
    -- where
        -- min = (1, 3)
        -- max = (1, 2)
igcd a b
    | a > 0 = igcd (b `rem` a) a
    | otherwise = b
-- boxes: 117161757, evals: 324440053 (nat 53%, alg 11%, lazy 26%, re 7%)  runtime 71.427 sec.
-- boxes: 48599259, evals: 93923764 (nat 57%, alg 0%, lazy 28%, re 14%)  runtime 22.152 sec.
-- Rang: 146                           

{--
    The number 145 is well known for the property that the sum of the 
    factorial of its digits is equal to 145:

    1! + 4! + 5! = 1 + 24 + 120 = 145
    
    Perhaps less well known is 169, in that it produces the longest chain of numbers 
    that link back to 169; it turns out that there are only three such loops that exist:
    
    169  363601  1454  169
    871  45361  871
    872  45362  872
    
    It is not difficult to prove that EVERY starting number will eventually 
    get stuck in a loop. For example,
    
    69  363600  1454  169  363601 ( 1454)
    78  45360  871  45361 ( 871)
    540  145 ( 145)
    
    Starting with 69 produces a chain of five non-repeating terms, 
    but the longest non-repeating chain with a starting number below 
    one million is sixty terms.
    
    How many chains, with a starting number below one million, 
    contain exactly sixty non-repeating terms?
-}
problem74 limit len = length . filter ((<limit) . fst) $ list
    where
        ifac 0 = 1;   ifac 1 = 1;    ifac 2 = 2;     ifac 3 = 6; ifac 4 = 24; ifac 5 = 120
        ifac 6 = 720; ifac 7 = 5040; ifac 8 = 40320; ifac 9 = 362880; ifac n = product [1..n]
        initial = TM.fromList [(169, 3), 
                                    (363601, 3),
                                    (1454, 3),
                                 (871, 2), 
                                    (45361, 2),
                                    (45362, 2),
                                 (872, 2), (1, 1), (2, 1), (145,1)]
        complete = fold chain initial [1 .. (limit-1)]
        list = filter ((len==) . snd) (each complete)
        chain tree n
            | Just k  <- TreeMap.lookup tree n  = tree
            -- trace ("chain " ++ show n ++ "\n") = undefined
            | nn == n {-, 
              !(trace ("chain " ++ show n ++ " = 1\n"))-} = TreeMap.insert tree n 1
            | Just k  <- TreeMap.lookup tree nn {-, 
              !(trace ("chain " ++ show n ++ " = " ++ show k ++ "+1\n"))-} = TreeMap.insert tree n (1+k)
            | otherwise = chain (chain tree nn) n
            where
                ns = idigits n
                nn = isum . map ifac $ ns
                -- nns = sort (idigits nn)     
                
-- boxes: 1772250381, evals: 7455511750 (nat 37%, alg 17%, lazy 25%, re 19%)  runtime 616.791 sec.
-- boxes:   59400146, evals:  573111189 (nat 42%, alg 23%, lazy 17%, re 16%)  runtime  48.015 sec.                
-- Rang 141

{--
    It turns out that 12 cm is the smallest length of wire that can be bent 
    to form an integer sided right angle triangle in exactly one way, but there are many more examples.

    12 cm: (3,4,5)      2*3*4
    24 cm: (6,8,10)     2*2*3*4
    30 cm: (5,12,13)    2*3*5
    36 cm: (9,12,15)    2*3*2*3
    40 cm: (8,15,17)    2*2*2*5
    48 cm: (12,16,20)   2*2*2*3*4
    
    120                 2*2*3*4*5
    
    In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, 
    and other lengths allow more than one solution to be found; for example, 
    using 120 cm it is possible to form exactly three different integer sided right angle triangles.
    
    120 cm: (30,40,50), (20,48,52), (24,45,51)
    
    Given that L is the length of the wire, 
    for how many values of L <= 2,000,000 can exactly one 
    integer sided right angle triangle be formed?
-}
problem75tooslow lim = length . filter (single . triplets) $ [1..lim]
    where
        single [x] = true
        single _   = false
        triplets n = [ (a+b+c, (a,b,c)) | 
                    a <- [1.. n `quot` 3],
                    b <- takeWhile (\b -> 2*b+a < n) [a..n],
                    c = n - b - a, 
                    a*a+b*b == c*c 
                  ]
        -- nix = 0
-- 50 sec. for limit = 1000!!!
-- find all triplets where a+b+c <= limit
-- still too slow, 1s for 1000, 60s for 10000
problem75stillslow n  = length . filter ((1==) . length) . group . sort $ {-[ a+b+c |
        a <- (1.. n `div` 3),
        b <- takeWhile (\b -> 2*b+a < n) (a..n),
        Right c <- [intIsSquare (a*a+b*b)],
        a+b+c <= n ]-} loop 1 1
    where
        loop a b
            | a > n `quot` 3 = []
            | 2*b + a >= n = loop (a+1) (a+1)
            | Right c <- intIsSquare (a*a+b*b), a+b+c <= n = a+b+c : loop a (b+1)
            | otherwise = loop a (b+1)
        group [] = []
        group [x] = [[x]]
        group (as@a:_) = takeWhile (a==) as : group (dropWhile (a==) as) 

-- create primitive triplets systematically according to formula
-- s = 2..., t = 2,4, ..., s(-1) if s is odd, else 1,3, ..., s-1 if s is even
-- a = 2*s*t, b = s - t, c = s + t
-- if a + b + c <= limit then 2*s*t + s - t + s + t <= limit
--                            2*s*t + 2*s <= limit
-- then multiply to find multiples
-- takes 14 sec to find all triplets up to 2000000
-- with sort, group and count, it needs 600MB and 148 sec.
-- with group, partition and count, it needs 500MB and takes ages
-- with tree, it does not complete with 1g
{-
problem75 n  = -- length <~ filter ((1==) <~ length) <~ group <~ sort 
               -- length <~ filter ((1==) <~ length) <~ group
               -- length <~ filter ((1==) <~ snd)    <~ flip TreeMap.keyvalues Eq <~ fold collect TreeMap.Nil
               -- length <~ filter (1==) <~ gcount <~ sort 
               countarr 0 0 <~ foldM collarr arr
    $ [ i*abc |
        s <- takeWhile (\s -> 2*s   + 2*s*s <= n) (iterate (1+) 2),
        t <- takeWhile (\t -> t<s && 2*s*t + 2*s*s <= n) (iterate (2+) (1 + s `rem` 2)),
        igcd s t == 1,  -- forgot that before
        let { a = 2*s*t; b = s*s-t*t; c = s*s+t*t; abc = a+b+c },
        i <- takeWhile (\i -> i*abc <= n) (iterate (1+) 1) ]
        
    where
        arr = ST.run (IntArr.new (n+1) >>= our)
        collarr (arr::IntArr) n = do arr.[n <- arr.[n]+1]
        countarr acc i (arr::IntArr)
            | i > n = acc
            | arr.[i] == 1 = countarr (acc+1) (i+1) arr
            | otherwise = countarr acc (i+1) arr
        collect tree num = TreeMap.insert tree num count
            where count
                    | Just n <- TreeMap.lookup tree num = n+1
                    | otherwise                      = 1
        gcount [] = []
        gcount [x] = [1]
        gcount (as@a:_) = length (takeWhile (a==) as) : gcount (dropWhile (a==) as)                     
        group [] = []
        group [x] = [[x]]
        group (xs@a:_) = as : group bs where (as, bs) = partition (a==) xs
-- boxes: 218816197, evals: 739514633 (nat 24%, alg 8%, lazy 31%, re 35%)  runtime 147.119 sec. WRONG ANSWER.
-- values above are for the case where i forgot that s and t must not have common divisors, now we have
-- boxes: 186144674, evals: 626369636 (nat 24%, alg 8%, lazy 31%, re 35%)  runtime 127.084 sec.
-- boxes: 9460069, evals: 41813880 (nat 16%, alg 0%, lazy 34%, re 49%)  runtime 11.364 sec. with array stuff
-- Rang 137
-}

problem76Brute n = nWTC n (reverse [1..n-1])
-- boxes: 6032610492, evals: 9606206049 (nat 52%, alg 17%, lazy 15%, re 15%)  runtime 457.671 sec.

{-
--- euler partition function
part 0 = 1n
part n 
    | n < 0 = 0n
    | otherwise = p (Array.new (n+1)) (toInteger n)
    where
        p :: Array Integer -> Integer -> Integer
        p cache n 
            | n < 0n  = 0n
            | n == 0n = 1n
            | Just r <- cache.[n.int] = r
            | otherwise = do
                    let r = sum <~ takeWhile (0n!=) <~ map term $ (iterate succ 1)
                    cache.[n.int <- r]
                    return r
            where 
                term k = (if k `rem` 2 != 0 then 1n else negate 1n) * ( p cache (n - f k) + p cache (n - f (negate k)))
                f k
                    | k < 0 = bk * (3n*bk + 1n) `div` 2n
                    | k > 0 = bk * (3n*bk - 1n) `div` 2n
                    where bk = toInteger (abs k)

problem76 n = part n - 1n
-- boxes: 8789, evals: 21323 (nat 23%, alg 0%, lazy 41%, re 35%)  runtime 0.054 sec.
-- Rang 132
-}        

{-
        It is possible to write ten as the sum of primes in exactly five different ways:
        
        7 + 3
        5 + 5
        5 + 3 + 2
        3 + 3 + 2 + 2
        2 + 2 + 2 + 2 + 2
        
        What is the first value which can be written as the sum of primes in over five thousand different ways?
-}

-- this is the same as the coin changing problem
-- boxes: 2564785, evals: 4221177 (nat 52%, alg 17%, lazy 14%, re 15%)  runtime 0.256 sec.
-- Rang 199
problem77 lim = takeWhile ((<=lim) . snd)  [ (k, pk) | k <- (iterate succ 2), pk = nWTC k ((reverse . takeWhile (<=k)) iprimes) ]  

{-
    Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.
    
    OOOOO 
    OOOO   O 
    OOO   OO 
    OOO   O   O 
    OO   OO   O 
    OO   O   O   O 
    O   O   O   O   O 
    
    Find the least value of n for which p(n) is divisible by one million.
-}
-- Rang: 194
-- boxes: 92856627, evals: 249678290 (nat 28%, alg 0%, lazy 40%, re 31%)  runtime 76.348 sec.
{-
problem78 lim = head [ (k, pnk) | k <- iterate succ 1, pnk = part k, pnk `mod` lim == 0n ]
    -- euler partition function
    where
        part 0 = 1n
        part n 
            | n < 0 = 0n
            | otherwise = ST.run (doit n)
        doit n = do
            parr <- STArray.new 1000000
            p parr (toInteger n)
        
        p :: STArray Integer s -> Integer -> ST s Integer
        p cache n 
            | n < 0n  = return 0n
            | n == 0n = return 1n
            | otherwise = do
                mbr <- cache.[n.int]
                case mbr of
                    Just r -> return r
                    other ->  do
                        let r = sum <~ takeWhile (0n!=) <~ map term $ (iterate succ 1)
                        cache.[n.int <- r]
                        return r
            where 
                term k = (if k `rem` 2 != 0 then 1n else negate 1n) * ( p cache (n - f k) + p cache (n - f (negate k)))
                f k
                    | k < 0 = bk * (3n*bk + 1n) `div` 2n
                    | k > 0 = bk * (3n*bk - 1n) `div` 2n
                    | otherwise = undefined
                    where bk = toInteger (abs k)
-}
{---
    A common security method used for online banking is to ask the user for three random characters from a passcode. 
    For example, if the passcode was 531278, they may asked for the 2nd, 3rd, and 5th characters; 
    the expected reply would be: 317.
    
    The text file, keylog.txt, contains fifty successful login attempts.

    Given that the three characters are always asked for in order, 
    analyse the file so as to determine the shortest possible secret passcode of unknown length.
-}
problem79 = 73162890 -- where
    -- logins = [ 319,680,180,690,129,620,762,689,762,
    --        318,368,710,720,710,629,168,160,689,
    --        716,731,736,729,316,729,729,710,769,290,719,
    --        680,318,389,162,289,162,718,729,319,790,  
    --        680,890,362,319,760,316,729,380,319,728,716]
    -- place1 = uniq . sort . map (`div` 100) $ logins
    -- place2 = uniq . sort . map (`div` 10) . map (`mod` 100) $ logins
    -- place3 = uniq . sort . map (`mod` 10)  $ logins
    -- 7 316289 0
-- boxes: 5050, evals: 17216 (nat 24%, alg 12%, lazy 32%, re 31%)  runtime 0.022 sec.
-- Rang: 191    

{-
    It is well known that if the square root of a natural number is not an integer, then it is irrational. 
    The decimal expansion of such square roots is infinite without any repeating pattern at all.

    The square root of two is 1.41421356237309504880..., and the digital sum of the first one hundred decimal digits is 475.

    For the first one hundred natural numbers, find the total of the digital sums of the first one hundred decimal digits 
    for all the irrational square roots.
-}
type Decimal = (Integer, [Int])
problem80 i = isum [ (isum . take i . toDecimal . approx (i*10) . fracSqrt) n | 
                n <-  [2n..100n], irrat n]
    where
        irrat n
            | Left _ <- isSquare n = true
            | otherwise = false 
        toDecimal (a,b)
            | a >= b    = toDecimal (a, b*10n)           -- (a `div` b,  (remainder (a `mod` b) b))
            | otherwise = remainder a b
            where
                remainder :: Integer -> Integer -> [Int] 
                remainder a b = d : remainder a' b
                    where
                        a10 = a*10n
                        dn = a10 `div` b
                        a' = a10 - (b*dn)
                        d = dn.int
-- boxes: 623125, evals: 4015341 (nat 19%, alg 9%, lazy 37%, re 33%)  runtime 3.329 sec.
-- Rang 189      

{--
    In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, 
    by only moving to the right and down, is indicated in bold red and is equal to 2427.

    131 673 234 103  18    131  804 1038 1141 1159 
    201  96 342 965 150    332  428  770  
    630 803 746 422 111    962 1231 
    537 699 497 121 956   1499
    805 732 524  37 331 
     
     
    
    Find the minimal path sum, in matrix.txt (right click and 'Save Link/Target As...'), a 31K text file containing a 80 by 80 matrix, 
    from the top left to the bottom right by only moving right and down.


-}
{-
problem81 file = num (go array topleft) botright -- join "\n" (map (show <~ Array.toList) (go array topleft).toList)
    where
        go :: Array (Array Long) -> (Int, Int) -> Array (Array Long)
        go arr adr
            -- | trace ()          = undefined
            | adr == botright   = uarr
            | good next         = go uarr next          -- schräg hoch
            | good (down start) = go uarr (down start)  -- nächste diagonale
            | otherwise         = go uarr (right start) -- nächste diagonale (nach unterer linker Ecke)
            where
                trace () = do stderr << joined "\n" (map (show <~ Array.toList) arr.toList) << "\n---\n"
                uarr = apply arr adr (mn+)
                mn = if adr == topleft then 0L else fold Long.min Long.maxBound <~ map (num arr) <~ filter good $ [up adr, left adr]
                next  =  up (right adr)
                start = (snd adr, fst adr)
        
        lines = case IO.BufferedReader.open file of
            Left exc -> error exc.getMessage
            Right br -> br.getlines
        numlines = map (map String.atol <~ ´,\s*´.splitted) lines
        array = Array.fromList (map Array.fromList numlines)
        topleft = (0,0)
        botright = (b, array.[!b].length - 1) where b = array.length - 1
        up   (i,j) = (i-1, j)
        left (i,j) = (i, j-1)
        down (i,j) = (i+1,j)
        right(i,j) = (i, j+1)
        good (i,j) = i >= 0 && j >= 0 && i <= fst botright && j <= snd botright
        apply :: Array (Array Long) -> (Int, Int) -> (Long -> Long) -> Array (Array Long)
        apply array (i,j) f = array.[i = array.[!i].[j = f n]] where n = num array (i,j)
        num :: Array (Array Long) -> (Int, Int) -> Long
        num array (i,j)
            | good (i,j) = array.[!i].[!j]
            | otherwise  = error ("bad index: " ++ show (i,j))
-- boxes: 192881, evals: 956563 (nat 32%, alg 12%, lazy 22%, re 32%)  runtime 0.282 sec.
-- Rang: 182?             

main ["problem81", file]  = do stdout << problem81  file; stdout.println
-}
main ["problem80", si] | Right i <- si.int   = do println (problem80 i)
main ["problem79"]   = do println problem79                
-- main ["problem78", si] | Right i <- si.int   = do println (problem78 (toInteger i))
main ["problem77", si] | Right i <- si.int   = do println (problem77 i)                    
-- main ["problem76", si] | Right i <- si.int   = do println (problem76 i)                    
-- Problem75 currently disabled.
-- main ["problem75", si] | Right i <- si.int   = do println (problem75 i)            
main ["problem74", si, sj] | Right i <- si.int, 
                             Right j <- sj.int   = do println (problem74 i j)
main ["problem73", si] | Right i <- si.int   = do println (problem73 i)
main ["problem72", si] | Right i <- si.int   = do println (problem72 i)
main ["problem71", si] | Right i <- si.int   = do println (problem71 i)
main ["problem70", si] | Right i <- si.int   = do println (problem70 i)
main ["problem69", si] | Right i <- si.int   = do println (problem69 i)
main ["problem68", si] | Right i <- si.int   = do println (problem68 i)
main ["problem67", file]  = do r <- problem67  file; println r
main ["problem66", si] | Right i <- si.int   = do println (problem66 i)
main ["problem65"]   = do println (problem65)
main ["problem64", si] | Right i <- si.int   = do println (problem64 i)
main ["problem63"]   = do println problem63
main ["problem62", si] | Right i <- si.int   = do println (problem62 i)
main ["problem70", si] | Right i <- si.int   = do println (problem70 i)
-- main ["problem61"]   = do stdout << problem61; stdout.println            
-- main ["problem60"]   = do stdout << problem60; stdout.println
-- main ["problem59"]   = do stdout << problem59; stdout.println
-- main ["problem57"]   = do stdout << problem57; stdout.println
-- main ["problem56"]   = do stdout << problem56; stdout.println                    
-- main ["problem55", si] | Right i <- si.int   = do stdout << problem55 i; stdout.println
-- main ["problem53", si] | Right i <- si.int   = do stdout << problem53 i; stdout.println
-- main ["problem52"]   = do stdout << problem52; stdout.println                    
-- main ["problem51", si] | Right i <- si.int   = do stdout << problem51 i; stdout.println
main ["problem50", si] | Right i <- si.int   = do println (problem50 i)
-- main ["problem49"]   = do stdout << problem49; stdout.println
-- main ["problem48", si] | Right i <- si.int   = do stdout << problem48 i; stdout.println 
-- main ["problem47", si] | Right i <- si.int   = do stdout << problem47 i; stdout.println 
-- main ["problem46", si] | Right i <- si.int   = do stdout << problem46 i; stdout.println
-- main ["problem45"]   = do stdout << problem45; stdout.println
-- main ["problem44", si] | Right i <- si.int   = do stdout << problem44 i; stdout.println
-- main ["problem43"]   = do stdout << problem43; stdout.println
-- main ["problem42", file]  = do stdout << problem42  file; stdout.println
-- main ["problem41"]   = do stdout << problem41; stdout.println
-- main ["problem40"]   = do stdout << problem40; stdout.println
main ["problem39", si] | Right i <- si.int   = println $  problem39 i
-- main ["problem38"]   = do stdout << problem38; stdout.println
-- main ["problem37"]   = do stdout << problem37; stdout.println
-- main ["problem36", si] | Right i <- si.int   = do stdout << problem36 i; stdout.println
-- main ["problem35", si] | Right i <- si.int   = do stdout << problem35 i; stdout.println
-- main ["problem4"]   = do stdout << problem4; stdout.println
main ["problem9"] = println problem9
-- main ["problem10"]  = do stdout << problem10; stdout.println
-- main ["problem11"]  = do stdout << problem11; stdout.println
-- main ["problem11i"]  = do stdout << iproblem11; stdout.println
-- -- main ["problem14e"]  = do stdout << problem14e for stdout.println
-- -- main ["problem14m", si] | Right i <- si.int = do stdout << problem14m i; stdout.println
-- main ["problem14f", si] | Right i <- si.int = do stdout << problem14f i; stdout.println
-- main ["problem18"]  = do stdout << problem18; stdout.println
-- main ["problem19"]  = do stdout << problem19; stdout.println
-- main ["problem20"]  = do stdout << problem20; stdout.println
-- main ["problem21"]  = do stdout << problem21; stdout.println
-- main ["problem22", file]  = do stdout << problem22  file; stdout.println
main ["problem23"]  = println problem23
-- main ["problem24"]  = do stdout << problem24; stdout.println
main ["problem25", si] | Right i <- si.int   = println (problem25 i)
-- main ["problem26"]  = do stdout << problem26; stdout.println
-- main ["problem27", si] | Right i <- si.int   = do stdout << problem27 i; stdout.println
-- main ["problem29", si] | Right i <- si.int   = do stdout << problem29 i; stdout.println
-- main ["problem30", si] | Right i <- si.int   = do stdout << problem30 i; stdout.println
-- main ["problem31", si] | Right i <- si.int   = do stdout << problem31 i; stdout.println
-- main ["problem32"]  = do stdout << problem32; stdout.println
main ["problem33"]  = println problem33
-- main ["problem34"]  = do stdout << problem34; stdout.println

main _ = println "Try java Euler problemNN"
